Problems

# Sum of distances

# Sum of distances

You are given a weighted tree with n vertices and n - 1 edges. The distance between the vertices u and v is the weight of the smallest edge on the path between u and v.

Find the sum of the distances between all pairs of tree vertices.

## Input data

The first line contains the single integer number n~(2 \le n \le 10^5) — the number of vertexes in graph. It is followed by n - 1 lines containing the description of the edges. Every line of description consists of three integer numbers: vertices connected by the edge (labeled from 1 to n) and edge’s weight.

## Output data

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

## Examples

Input example #1

3 1 2 1 1 3 3

Output example #1

5

Input example #2

5 1 3 7 4 1 2 4 5 5 2 4 3

Output example #2

30