問題文

$N$頂点の木があります。 この木の$i(1\le i\le N-1)$番目の辺は頂点$u_i$と頂点$v_i$を双方向に結んでいて、その長さは$w_i$です。
頂点$s$と頂点$t$の最短距離を$d_{s,t}$とします。$\sum _{s=1}^N\sum _{t=1}^N{d}_{s,t}$を求めてください。なお$d_{i,i}=0(1\le i\le N)$とします。

入力

$N$
$u_1{v}_1{w}_1$
$u_2{v}_2{w}_2$
$⋮$
$u_{N-1}{v}_{N-1}{w}_{N-1}$

$2\le N\le 2\times {10}^5$
$1\le u_i,v_i\le N(1\le i\le N-1)$
$1\le w_i\le 100(1\le i\le N-1)$
与えられるグラフは木である。

出力

答えを一行で出力してください。最後に改行してください。

サンプル

3
1 2 1
2 3 2

12

5
2 5 2
2 3 10
1 3 8
3 4 7

256