#P2022D. Accumulation Degree

    ID: 115 Type: Default 1000ms 256MiB Tried: 7 Accepted: 6 Difficulty: 9 Uploaded By: Tags>福建师范大学第19届程序设计竞赛

Accumulation Degree

Accumulation Degree

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

After days of heavy rain, FJNU was flooded into an undirected tree with nn nodes numbered from 11 to nn. The rain also formed ponds on the road making it difficult to walk. More precisely, there are n1n-1 roads in this tree, the ii-th (1in1)(1 \leq i \leq n-1) edge connects node uiu_i and node viv_i and it has a weight wiw_i means there is ponding with degree wiw_i on this road.

Liu Wei, the clever Peppa Pig was forced by Tai Liang to calculate the accumulation degree of this tree:

For different node uu and vv, let f(u,v)f(u,v) be the greatest weight edge in the shortest path from node uu to node vv.

Liu Wei needs to calculate i=1n1j=i+1nf(i,j)\sum^{n-1}_{i=1}\sum^{n}_{j=i+1}f(i,j).

As a full stack developer, Liu Wei has more important things to do, so you are asked to help him solve this problem.

Input

The first line contains one integers n(2n105)n(2\leq n\leq 10^5).

In the following n1n-1 lines, each line contains three integers $u_i,v_i,w_i(1 \leq u_i,v_i \leq N,1 \leq w_i \leq 10^7)$ denoting there is an edge between node uiu_i and viv_i with a weight wiw_i.

Output

Print a single integer, denoting the answer to the question.

3
1 2 10
2 3 20
50