Central Tree

A tree is a connected graph with no cycles.

Call a vertex a central vertex if the sum of the (weighted) distances from it to every other vertex is as small as possible. When the number of vertices is small, you can find it easily by trying every vertex one by one.

For example, consider the following tree with 5 vertices. Name the vertices $A, B, C, D, E$; the edges and their weights are:

• $B - A$ : 2
• $B - C$ : 1
• $B - D$ : 7
• $D - E$ : 5

Here the central vertex is $B$. The distances from $B$ to each vertex are $B \to A = 2,\quad B \to C = 1,\quad B \to D = 7,\quad B \to E = 7 + 5 = 12$ so their sum is $2 + 1 + 7 + 12 = 22$.

Write a program that, even when the number of vertices $N$ is large, reads a tree and computes the sum of the distances from every vertex to the central vertex (that is, the minimum possible sum defined above).

The input consists of several test cases. The first line of each test case contains the number of vertices $n$ of the tree. ($1 \le n \le 10{,}000$) The vertices are numbered from $0$ to $n-1$.

Each of the following $n-1$ lines contains three integers $a$, $b$, and $w$. ($1 \le w \le 100$) This denotes an edge of weight $w$ connecting vertices $a$ and $b$.

The last line of the input contains a single $0$, marking the end of the input.

For each test case, print on its own line the sum of the distances from every vertex to the central vertex (the minimum possible sum).