Lalit is in an amusement park. There are N islands in this park. These islands are connected with each other by bridges. For each pair of islands (a; b) there is exactly one way to go from a to b or vice versa. The bridges are of varying lengths. Lalit wants to traverse the paths between all possible pairs of vertexes. For example, if there are 4 vertexes numbered 1 to 4, he wants to go from 1 to 2, then from 1 to 3, then from 1 to 4, then from 2 to 3, then from 2 to 4, and finally from 3 to 4. Each time he starts a traversal, he buys an energy drink which gives him K units of energy. He must buy that drink for which K is at least equal to the length of the minimum bridge in the path he is going to traverse. The energy drink costs 1 unit of money per 1 unit of energy. So a drink with K units of energy will cost K units of money. Can you tell Lalit the minimum cost he will have to bear for completing this adventure.

Input

The rst line of input will contain an integer N, i.e., the number of islands.

The next N-1 lines will contain 3 space-separated integers x, y and l denoting that island x and island y are connected by bridge a bridge of length l.

Output

Output the minimum cost that Lalit will have to bear in order to complete his adventure.

Test Data

In all the subtasks, the integers x and y are in the range [1;N]. Integer l is in the range [1; 10^6].

Subtask 1 (20 Points): 1 < N < 300.

Subtask 2 (80 Points): 1 < N < 10^6.

Sample Input

4
1 2 2
2 3 1
2 4 3

Sample Output

10

Best solution I can think of is N^2, hints appreciated.