Felix Halim .NET  
Google 

ACM/ICPC Indonesia National Contest 2007

Problem H

Tree Median

Time Limit: 3s


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

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.

Output

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

Sample Input

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

Sample Output

22
21


Problem Setter: Suhendry Effendy


Kembali ke pembahasan soal ini

Lihat problem lain:

  1. Minimum Swap
  2. GCD!
  3. Playing With Domino
  4. Email from the Professor
  5. Panda Number
  6. Jakarta Traffic Jam
  7. Sultan's Land
  8. Tree Median


© Felix Halim 2009 (Loaded in 0.00207 secs)