Minimum Total Adjustment Cost on a Tree

You are given a tree with N nodes where each edge connects two nodes with an associated positive weight. The tree is described by N - 1 edges. Each edge is represented by three integers: u, v, and w where w is the weight of the edge connecting nodes u and v.

To make all nodes in the tree have the same positive value, you must pay a cost equal to the weight of the edge to adjust the difference between the two connected nodes. It turns out that the minimum total cost to achieve this is equal to the sum of the weights of all edges. This is because, in a tree, every edge contributes exactly once to the adjustment cost.

Your task is to compute and output the minimum total adjustment cost required.

Note: All edge weights are positive integers and the given edges form a valid tree.

inputFormat

The first line contains an integer N (2 ≤ N ≤ 10⁵), the number of nodes in the tree. Each of the next N - 1 lines contains three space-separated integers u, v and w (1 ≤ u, v ≤ N, 1 ≤ w ≤ 10⁹), representing an edge between nodes u and v with weight w.

outputFormat

Output a single integer: the minimum total adjustment cost required to make all nodes equal, which is the sum of all the edge weights in the tree.

3
1 2 4
2 3 3

7