Valerian was captured by Shapur. The victory was such a great one that Shapur decided to carve a scene of Valerian's defeat on a mountain. So he had to find the best place to make his victory eternal!

He decided to visit all n cities of Persia to find the best available mountain, but after the recent war he was too tired and didn't want to traverse a lot. So he wanted to visit each of these n cities at least once with smallest possible traverse. Persian cities are connected with bidirectional roads. You can go from any city to any other one using these roads and there is a unique path between each two cities.

All cities are numbered 1 to n. Shapur is currently in the city 1 and he wants to visit all other cities with minimum possible traverse. He can finish his travels in any city.

Help Shapur find how much He should travel.

Input

First line contains a single natural number n (1 ≤ n ≤ 105) — the amount of cities.

Next n - 1 lines contain 3 integer numbers each xi, yi and wi (1 ≤ xi, yi ≤ n, 0 ≤ wi ≤ 2 × 104). xi and yi are two ends of a road and wi is the length of that road.

Output

A single integer number, the minimal length of Shapur's travel.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Examples

Input

3
1 2 3
2 3 4


Output

7


Input

3
1 2 3
1 3 3


Output

9
import java.io.IOException;
import java.io.FilterInputStream;
import java.util.Iterator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Zyflair Griffane
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputUtil in = new InputUtil(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		CF_Task solver = new CF_Task();
		solver.solve(1, in, out);
		out.close();
	}
}

class CF_Task implements DFSable {

    long to[];
    long res[];
    CostGraph g;

    public void solve(int testNumber, InputUtil in, PrintWriter out) {
        int vertices = in.nextInt();

        this.res = new long[vertices];
        this.to = new long[vertices];
        this.g = in.nextUndirectedCostGraph(vertices, vertices - 1, 1);

        DFSUtil.run(this, 0);
        for (int c: g.cost) {
            res[0] -= c;
        }
        out.println(-res[0]);
    }

    public SimpleGraph g() {
        return g;
    }

    public void start(int u) {   }

    public void preTraversal(int u, int v, int e) {
        to[v] = g.cost(e);
    }

    public boolean canTraverse(int u, int v, int e) {
        return true;
    }

    public void postTraversal(int u, int v) {   }

    public void end(int u, int par) {
        res[par] = Math.max(res[par], res[u] + to[u]);
    }
}

interface DFSable {
    public SimpleGraph g();
    public void start(int u);
    public void preTraversal(int u, int v, int e);
    public boolean canTraverse(int u, int v, int e);
    public void postTraversal(int u, int v);
    public void end(int u, int par);
}

class CostGraph extends SimpleGraph {

    public IntArrayList cost;

    public CostGraph(int vertexCount) {
        this(vertexCount, 16);
    }

    public CostGraph(int vertexCount, int edgeCount) {
        super(vertexCount, edgeCount);
        this.cost = new IntArrayList(edgeCount);
    }

    public int cost(int edge) {
        return cost.get(edge);
    }

    public void addUndirectedEdge(int u, int v, int edgeCost) {
        addDirectedEdge(u, v, edgeCost);
        addDirectedEdge(v, u, edgeCost);
    }

    public void addDirectedEdge(int u, int v, int edgeCost) {
        super.addDirectedEdge(u, v);
        cost.add(edgeCost);
    }

}

class InputUtil {

    JoltyScanner in;

    public InputUtil(InputStream istream) {
        in = new JoltyScanner(istream);
    }

    public String next() {
        return in.next();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public CostGraph nextUndirectedCostGraph(int vertices, int edges, int delta) {
        CostGraph res = new CostGraph(vertices, edges << 1);
        for (int i = 0; i < edges; i++) {
            int u = in.nextInt() - delta;
            int v = in.nextInt() - delta;
            int cost = in.nextInt();
            res.addUndirectedEdge(u, v, cost);
        }
        return res;
    }

}

class DFSUtil {
    public static void run(DFSable f, int src) {
        run(f, src, new boolean[f.g().vertexCount], new IntDeque());
    }
    public static void run(DFSable f, int src, boolean[] visited, IntDeque stk) {

        if (visited[src]) {
            return;
        }

        SimpleGraph g = f.g();

        stk.push(-1);
        stk.push(src);
        visited[src] = true;

        Iterator<Integer>[] adj = new Iterator[g.vertexCount];
        int last = -1;
        Loop: while (true) {
            int u = stk.poll();
            if (u == -1) {
                break;
            }
            if (adj[u] == null) {
                f.start(u);
                adj[u] = g.edges[u].iterator();
            }
            else {
                f.postTraversal(u, last);
            }
            last = u;
            while (adj[u].hasNext()) {
                int e = adj[u].next();
                int v = g.to(e);
                if (v != stk.peek()) {
                    f.preTraversal(u, v, e);
                }
                if (!visited[v] && f.canTraverse(u, v, e)) {
                    visited[v] = true;
                    stk.push(u);
                    stk.push(v);
                    continue Loop;
                }
            }
            if (stk.peek() != -1) {
                f.end(u, stk.peek());
            }
        }
    }
}

class SimpleGraph {

    public IntArrayList to;
    public IntDeque edges[];
    public int vertexCount;
    public int edgeCount;

    public SimpleGraph(int vertexCount) {
        this(vertexCount, 16);
    }

    public SimpleGraph(int vertexCount, int edgeCount) {
        this.to = new IntArrayList(edgeCount);
        this.edges = new IntDeque[vertexCount];
        this.vertexCount = vertexCount;
        this.edgeCount = 0;
//        this.inDegree = new int[vertexCount];
//        this.outDegree = new int[vertexCount];
        for (int i = 0; i < vertexCount; i++) {
            edges[i] = new IntDeque();
        }
    }

    public void addDirectedEdge(int u, int v) {
        to.add(v);
        edges[u].add(edgeCount);
//        inDegree[v]++;
//        outDegree[u]++;
        edgeCount++;
    }

    public int to(int edge) {
        return to.get(edge);
    }

}

class IntArrayList implements Iterable<Integer> {
    int size = 0;
    int[] array;

    public IntArrayList() {
        this(16);
    }

    public IntArrayList(int length) {
        array = new int[length];
    }

    public <T extends Iterable<Integer>> IntArrayList(T intList) {
        this(16);
        addAll(intList);
    }

    public void add(int element) {
        ensureCapacity();
        array[size] = element;
        size++;
    }

    public <T extends Iterable<Integer>>void addAll(T intList) {
        for (int i: intList) {
            add(i);
        }
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("" + index);
        }
    }

    public void ensureCapacity() {
        if (size == array.length) {
            int[] newArray = new int[size << 1];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }

    public int get(int index) {
        checkIndex(index);
        return array[index];
    }

    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int index = 0;
            public boolean hasNext() {
                return index < size;
            }
            public Integer next() {
                return array[index++];
            }
            //FIXME - Never tested
            public void remove() {
                if (index == 0) {
                    throw new IndexOutOfBoundsException();
                }
                index--;
                System.arraycopy(array, index + 1, array, index, size - index);
                size--;
            }
        };
    }

    public String toString() {
        if (size == 0) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        for (int i: this) {
            res.append(i);
            res.append(" ");
        }
        res.setLength(res.length() - 1);
        return res.toString();
    }

}

class IntDeque implements Iterable<Integer> {

    private int capacity;
    private int size = 0;
    private int front = 0;
    private int back = 0;
    private int[] deque;
    public IntDeque() {
        this(16);
    }
    public IntDeque(int capacity) {
        this.capacity = capacity;
        deque = new int[capacity];
    }

    public <T extends Iterable<Integer>>IntDeque(T intList) {
        this(16);
        addAll(intList);
    }
    public IntDeque(int[] intArr) {
        this(16);
        for (int i: intArr) {
            addLast(i);
        }
    }
    public void add(int x) {
        addLast(x);
    }
    public <T extends Iterable<Integer>>void addAll(T intList) {
        for (int i: intList) {
            addLast(i);
        }
    }
    public void addLast(int x) {
        ensureCapacity();
        size++;
        deque[back++] = x;
        if (back == capacity) {
            back = 0;
        }
    }
    public void addFirst(int x) {
        ensureCapacity();
        size++;
        if (front == 0) {
            front = capacity;
        }
        deque[--front] = x;
    }

    public void ensureCapacity() {
        if (size < capacity) {
            return;
        }
        int[] newDeque = new int[capacity << 1];
        for (int i = 0, j = front; i < size; i++, j++) {
            if (j == capacity) {
                j = 0;
            }
            newDeque[i] = deque[j];
        }
        deque = newDeque;
        capacity <<= 1;
        front = 0;
        back = size;
    }

    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int done = 0;
            int curr = front;
            public boolean hasNext() {
                return done < size;
            }
            public Integer next() {
                Integer res = deque[curr++];
                if (curr == capacity) {
                    curr = 0;
                }
                done++;
                return res;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
    public int peek() {
        return peekFirst();
    }
    public int peekFirst() {
        return deque[front];
    }

    public int poll() {
        return pollFirst();
    }
    public int pollFirst() {
        if (size == 0) {
            throw new RuntimeException("IntDeque is empty!");
        }
        size--;
        int res = deque[front++];
        if (front == capacity) {
            front = 0;
        }
        return res;
    }

    public void push(int x) {
        addFirst(x);
    }

    public String toString() {
        if (size == 0) {
            return "";
        }
        StringBuilder res = new StringBuilder();
        for (int i: this) {
            res.append(i);
            res.append(" ");
        }
        res.setLength(res.length() - 1);
        return res.toString();
    }
}

class JoltyScanner {
    public static final int BUFFER_SIZE = 1 << 16;
	public static final char NULL_CHAR = (char) -1;

	StringBuilder str = new StringBuilder();
	byte[] buffer = new byte[BUFFER_SIZE];
	boolean EOF_FLAG = false;
	int bufferIdx = 0, size = 0;
	char c = NULL_CHAR;
	BufferedInputStream in;

	public JoltyScanner(InputStream in) {
		this.in = new BufferedInputStream(in, BUFFER_SIZE);
	}

	public int nextInt() {
		long x = nextLong();
		if (x > Integer.MAX_VALUE || x < Integer.MIN_VALUE) {
			throw new ArithmeticException("Scanned value overflows integer");
		}
		return (int) x;
	}

	public long nextLong() {
		boolean negative = false;
		if (c == NULL_CHAR) {
			c = nextChar();
		}
		for (; !EOF_FLAG && (c < '0' || c > '9'); c = nextChar()) {
			if (c == '-') {
				negative = true;
			}				
		}
		checkEOF();
		long res = 0;
		for (; c >= '0' && c <= '9'; c = nextChar()) {
			res = (res << 3) + (res << 1) + c - '0';
		}
		return negative ? -res : res;
	}

    public String next() {
		checkEOF();
		if (c == NULL_CHAR) {
			c = nextChar();
		}
		while (Character.isWhitespace(c)) {
			c = nextChar();
			checkEOF();
		}
		str.setLength(0);
		for (; !EOF_FLAG && !Character.isWhitespace(c); c = nextChar()) {
			str.append(c);
		}
		return str.toString();
	}

    public char nextChar() {
		if (EOF_FLAG) {
			return NULL_CHAR;
		}
		while (bufferIdx == size) {
			try {
				size = in.read(buffer);
				if (size == -1) {
					throw new Exception();
				}
			} catch (Exception e) {
				EOF_FLAG = true;
				return NULL_CHAR;
			}
			if (size == -1) {
				size = BUFFER_SIZE;
			}
			bufferIdx = 0;
		}
		return (char) buffer[bufferIdx++];
	}

    public void checkEOF() {
		if (EOF_FLAG) {
			throw new EndOfFileException();
		}
	}

	public class EndOfFileException extends RuntimeException {
	}
}

