A weighted tree with n vertices and n−1 edges is given. The distance between vertices u and v is defined as the weight of the smallest edge on the path between u and v.
Find the sum of distances between all pairs of vertices in the tree.
The first line contains the number of vertices n (2≤n≤105) 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 1 to n) and the weight of the edge.
Print the sum of distances between all pairs of vertices in the tree.