There are $n$ countries on planet W. For the sake of economic development, they have decided to build bidirectional roads between the countries to ensure connectivity. However, the kings of each country are very stingy and are only willing to build exactly $n - 1$ bidirectional roads.
The construction of each road incurs a certain cost, which is equal to the length of the road multiplied by the absolute difference between the number of countries on either side of the road. For example, in the figure below, the road indicated by the dashed line has 2 countries on one side and 4 countries on the other. If the length of this road is 1, the cost is $1 \times |2 - 4| = 2$. The numbers in the circles represent the country IDs.
Due to the large number of countries, there are many possible road construction plans, and the construction cost for each plan is difficult to calculate manually. The kings have decided to find someone to design a piece of software that, given a construction plan, calculates the required cost. Please help the kings design such a piece of software.
Input
The first line contains an integer $n$, representing the number of countries on planet W. The countries are numbered from $1$ to $n$.
The next $n - 1$ lines describe the road construction, where the $i$-th line contains three integers $a_i$, $b_i$, and $c_i$, representing that the $i$-th bidirectional road is built between countries $a_i$ and $b_i$ with length $c_i$.
Output
Output a single integer representing the total cost required to build all the roads.
Examples
Input 1
6 1 2 1 1 3 1 1 4 2 6 3 1 5 2 1
Output 1
20
Constraints
The range and characteristics of all test data are shown in the table below:
| Test Case ID | Scale of $n$ | Constraints |
|---|---|---|
| 1 | $n = 2$ | $1 \le a_i, b_i \le n$ |
| 2 | $n = 10$ | $0 \le c_i \le 10^6$ |
| 3 | $n = 100$ | |
| 4 | $n = 200$ | |
| 5 | $n = 500$ | |
| 6 | $n = 600$ | |
| 7 | $n = 800$ | |
| 8 | $n = 1000$ | |
| 9 | $n = 10,000$ | |
| 10 | $n = 20,000$ | |
| 11 | $n = 50,000$ | |
| 12 | $n = 60,000$ | |
| 13 | $n = 80,000$ | |
| 14 | $n = 100,000$ | |
| 15 | $n = 600,000$ | |
| 16 | $n = 700,000$ | |
| 17 | $n = 800,000$ | |
| 18 | $n = 900,000$ | |
| 19 | $n = 1,000,000$ | |
| 20 | $n = 1,000,000$ |