問題文

$N$ 頂点 $M$ 辺の単純かつ連結な無向グラフがあります。

各辺には重みという非負整数のパラメータが設定されています。 $i$ 番目の辺は頂点 $a_i,b_i$ を双方向に結び、重みは $w_i$ です。

頂点のペア $(u,v) \ (u < v)$ のコストを、頂点 $u$ から頂点 $v$ に向かうパス全てを考えたときの、「パスに含まれる辺の重みの最大値」の最小値と定めます。

全ての異なる $2$ 頂点のペア $(u,v) \ (1 \leq u < v \leq N)$ に対するコストの総和を求めてください。

入力

$N\ M$
$a_1\ b_1\ w_1$
$\vdots$
$a_M\ b_M\ w_M$

• 入力は全て整数
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• $1 \leq w_i \leq 10^8$
• 与えられるグラフは単純かつ連結

出力

全ての異なる $2$ 頂点のペア $(u,v) \ (1 \leq u < v \leq N)$ に対するコストの総和を出力してください。

サンプル

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

14

10 16
9 10 8
4 8 16
1 5 19
6 7 16
6 10 4
7 10 5
2 4 19
3 10 19
2 5 13
1 6 9
8 10 20
4 6 13
3 6 5
3 5 1
6 9 6
5 10 6

468