18 3 s 128 MB

A tree is a connected graph containing no cycles. A vertex is called a median vertex if the total cost to reach all vertices is minimal. There could be more than one median vertex in a tree, that’s why we define median as the set of all median vertices. To find median in a tree with small number of vertices is fairly easy task as you can solve this by a simple brute force program.

In the left figure, we can see a weighted tree with 5 vertices. The tree median is {B} because the total cost from vertex B to all other vertices is minimal.

B-A = 2 B-D = 7 B-C = 1 B-E = 7 + 5 = 12 TOTAL = 2 + 1 + 7 + 12 = 22

What if the number of vertices is quite large? This might be a problem since brute force program cost too much time. Given a weighted tree with *N* vertices, output the total cost to reach all vertices from its median.

Input consists of several cases. Each case begins with an integer *n* (1<= *n* <= 10,000) denoting the number of vertices in a tree. Each vertex is numbered from 0...*n*-1. Each of the next *n*-1 lines contains three integers: *a*, *b*, and *w* (1<= *w* <= 100), which means *a* and *b* is connected by an edge with weight *w*.

Input is terminated when *n* is equal to 0. This input should not be processed.

For each case, output a line containing the sum of cost of path to all other vertices from the tree median.

## Sample Input | ## Sample Output |
---|---|

5 0 1 2 1 2 1 1 3 7 3 4 5 6 0 1 1 1 2 4 2 3 1 3 4 4 4 5 1 0 | 22 21 |