# Sum of distances

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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≤n≤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

Input #1

Answer #1

Input #2

Answer #2

Submissions 112

Acceptance rate 39%