Sum of distances#10761
A weighted tree with vertices and n - 1 edges is given. The distance between vertices and is defined as the weight of the smallest edge on the path between and .
Find the sum of distances between all pairs of vertices in the tree.
The first line contains the number of vertices n~(2 \le n \le 10^5) in the graph. The next n - 1 lines describe the edges. Each line contains three integers: the numbers of vertices connected by the edge (vertices are numbered from to ) and the weight of the edge.
Print the sum of distances between all pairs of vertices in the tree.
Example 1
Example 2