Problem Statement

There is a simple connected undirected graph with $N$ vertices and $M$ edges.

Each edge has a non-negative integer parameter called its weight. The $i$-th edge connects vertices $a_i,b_i$ bidirectionally and has weight $w_i$.

The cost of a pair of vertices $(u,v) \ (u < v)$ is defined as follows: considering all paths from vertex $u$ to vertex $v$, it is the minimum of "the maximum weight of the edges contained in the path".

Find the sum of the costs over all pairs of $2$ distinct vertices $(u,v) \ (1 \leq u < v \leq N)$.

Input

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

• All inputs are integers
• $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$
• The given graph is simple and connected

Output

Output the sum of the costs over all pairs of $2$ distinct vertices $(u,v) \ (1 \leq u < v \leq N)$.

Sample

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