该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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 $n$ nodes numbered from $1$ to $n$. The rain also formed ponds on the road making it difficult to walk. More precisely, there are $n-1$ roads in this tree, the $i$-th $(1 \leq i \leq n-1)$ edge connects node $u_i$ and node $v_i$ and it has a weight $w_i$ means there is ponding with degree $w_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 $u$ and $v$, let $f(u,v)$ be the greatest weight edge in the shortest path from node $u$ to node $v$.

Liu Wei needs to calculate $\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(2\leq n\leq 10^5)$.

In the following $n-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 $u_i$ and $v_i$ with a weight $w_i$.

Output

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

3
1 2 10
2 3 20

50