题目描述

$N$ 頂点の木があり、頂点は $1,\ 2,\ \dots,\ N$ と番号付けられています。
$i\ \,\ (1\ \leq\ i\ \leq\ N\ -\ 1)$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結び、重みは $w_i$ です。

異なる頂点 $u,\ v$ に対し、頂点 $u$ から頂点 $v$ までの最短パスに含まれる辺の重みの最大値を $f(u,\ v)$ とおきます。

$ \displaystyle\ \sum_{i\ =\ 1}^{N\ -\ 1}\ \sum_{j\ =\ i\ +\ 1}^N\ f(i,\ j) $ を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $u_1$ $v_1$ $w_1$ $\vdots$ $u_{N\ -\ 1}$ $v_{N\ -\ 1}$ $w_{N\ -\ 1}$

输出格式

答えを出力せよ。

题目大意

给出一个有$N−1$条边的树，求树上每两点之间最短路的最大权值边的和。

3
1 2 10
2 3 20

50

5
1 2 1
2 3 2
4 2 5
3 5 14

76

提示

制約

• $2\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ u_i,\ v_i\ \leq\ N$
• $1\ \leq\ w_i\ \leq\ 10^7$
• 与えられるグラフは木である。
• 入力は全て整数である。

Sample Explanation 1

$ f(1,\ 2)\ =\ 10,\ f(2,\ 3)\ =\ 20,\ f(1,\ 3)\ =\ 20 $ であるので、これらの和である $50$ を出力します。