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 finally 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**

41 2 22 3 12 4 3

**Sample Output**

10

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