Costly Road Construction on Planet W

On planet W, there are n countries. In order to boost their economies, all the kings agreed to build exactly n−1 bidirectional roads so that every country is connected. Because the road network is a tree, each road, when removed, will split the countries into two parts. The cost of building a road is determined by its length multiplied by the absolute difference between the number of countries on its two sides. Mathematically, for a road of length \(l\) that separates the tree into two parts with \(x\) and \(n-x\) countries respectively, the cost is given by:

\( cost = l \times |x - (n-x)| = l \times |2x - n| \)

Your task is to compute the total cost required for a given road construction plan.

inputFormat

The first line contains an integer \(n\) (\(2 \leq n \leq 10^5\)), the number of countries. Each of the following \(n-1\) lines contains three integers \(u\), \(v\) and \(l\), indicating that a bidirectional road of length \(l\) connects country \(u\) and country \(v\).

outputFormat

Output a single integer, the total cost to build all the roads according to the given construction plan.

sample

2
1 2 10

0