暂无测试数据。

我认为只要在集团生活中被讨厌了，就能一个人待着了

——五郎

少年们开始探索花园外的新世界。

他们发现新的世界是一张无向连通图。

定义一张无向连通图中无序点对 $(i,j)$ 的贡献为 所有可以从 $i$ 走到 $j$ 的简单路径中，经过的边的最大值。 其中简单路径是指不重复经过一条边或一个点的路径。

现在少年们想知道所有点对的贡献之和，请你帮助他们求出答案。

输入格式

第一行两个正整数 $n$，$m$，分别表示无向图的点数和边数.

接下来 $m$ 行，每行三个正整数 $u,v,w$，表示一条连接 $u,v$ ，边权为 $w$ 的无向边.

输出格式

一行一个整数，表示答案.

数据范围

对于 $20\%$ 的数据，$n\leq 10,m\leq 20$.

另有 $40\%$ 的数据，保证给出的是一棵树.

对于 $100\%$ 的数据，$n\leq 5\times 10^5,m\leq 6\times 10^5,1\leq w\leq 10^4$，保证给出的图联通且没有重边或自环。

本题输入量较大，建议使用读入优化

6 7
1 2 9
1 3 6
1 4 8
3 5 9
5 6 4
6 1 4
5 1 3

134

12 14
1 2 4
2 3 6
3 4 10
4 1 6
5 6 6
6 7 3
7 8 2
8 5 8
9 10 4
10 11 7
11 12 8
12 9 1
3 5 1
3 9 5

575