In ICPCCamp there were n towns conveniently numbered with
connected with (n - 1) roads.
The i-th road connecting towns and has length .
It is guaranteed that any two cities reach each other using only roads.

Bobo would like to build (n - 1) highways so that any two towns reach each using *only highways*.
Building a highway between towns x and y costs him cents,
where is the length of the shortest path between towns x and y using roads.

As Bobo is rich, he would like to find the most expensive way to build the (n - 1) highways.

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer n.
The i-th of the following (n - 1) lines contains three integers ,  and .

* 
* 
* 
* The number of test cases does not exceed 10.

For each test case, output an integer which denotes the result.

5
1 2 2
1 3 1
2 4 2
3 5 1
5
1 2 2
1 4 1
3 4 1
4 5 2

19
15