Sum of distances

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.

Input

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 $1$ to $n$) and the weight of the edge.

Output

Print the sum of distances between all pairs of vertices in the tree.

Examples