Dungeon (II)

You are involved in the development of a certain game. The game is for players to explore randomly generated dungeons. As a specification of the game, I want to show the player the danger level of the dungeon in advance and select whether to search for the generated dungeon or to regenerate a new dungeon.

There are n rooms in the dungeon generated by this game, and they are numbered from 0 to n-1. The rooms are connected by a passage. There are a total of n-1 passages connecting rooms. The passage can go in either direction. In addition, a distance is set between the rooms. In the generated dungeon, it is possible to go from one room to all other rooms via several passages. Then, when the player plays the game, two different rooms are selected as the start point and the goal point.

You decide to decide how to evaluate the risk in order to evaluate the dungeon. First, the risk level when moving from one room to another is set to the value of the most costly passage among the passages used to move between rooms in the shortest time. Then, we decided to set the risk level of the dungeon as the sum of the risk levels when moving between a pair of rooms where i <j.

A randomly generated dungeon is given as input. First, calculate the risk of moving for all room pairs where i <j. Then output the sum as the answer to the problem.

Input

The input is given in the following format.

n a1 b1 c1 .. .. .. an-1 bn-1 cn-1

ai bi ci means that the distance of the passage connecting the rooms ai and bi is ci.

Input meets the following constraints 2 ≤ n ≤ 200,000 0 ≤ ai, bi <n 0 ≤ ci ≤ 100,000

Output

Print the answer value on one line

Examples

Input

4 0 1 3 1 2 5 1 3 2

Output

23

Input

6 0 2 5 2 1 1 2 3 10 3 5 4 3 4 2

Output

111

inputFormat

input. First, calculate the risk of moving for all room pairs where i <j. Then

outputFormat

output the sum as the answer to the problem.

Input

The input is given in the following format.

n a1 b1 c1 .. .. .. an-1 bn-1 cn-1

ai bi ci means that the distance of the passage connecting the rooms ai and bi is ci.

Input meets the following constraints 2 ≤ n ≤ 200,000 0 ≤ ai, bi <n 0 ≤ ci ≤ 100,000

Output

Print the answer value on one line

Examples

Input

4 0 1 3 1 2 5 1 3 2

Output

23

Input

6 0 2 5 2 1 1 2 3 10 3 5 4 3 4 2

Output

111

样例

4
0 1 3
1 2 5
1 3 2

23