UltraNet 公司为全国的城市提供网络连接。对于任意一对城市，它们要么直接相连，要么间接相连。如果城市 $i$ 和城市 $j$ 之间架设了一条带宽为 $b_{i,j} = b_{j,i}$ 的电缆，则称它们直接相连。对于不直接相连的两个城市，它们之间至少存在一条路径。在当前的 UltraNet 网络中，一对城市之间可能存在多条路径。

当前的 UltraNet 运行良好，但每条电缆的维护费用昂贵。节能是另一个需要考虑的问题。电缆的能耗与其带宽成正比。因此，公司制定了一项优化计划，按照以下优先顺序对网络进行重组：

1. 在不牺牲整个 UltraNet 连通性的前提下，应使电缆数量最少。换句话说，必须满足每对城市之间恰好存在一条路径。
2. 如果存在多种使电缆数量最少的方法，则应使整个网络的瓶颈最大化。网络的瓶颈由带宽最窄的城市对决定，而城市对 $(i, j)$ 的带宽 $b'_{i,j}$ 由从 $i$ 到 $j$ 的唯一路径上带宽最窄的电缆决定。
3. 如果在满足上述两点后仍有多种方法，则应使网络的总能耗最小化。换句话说，应使剩余电缆的带宽之和最小。

你的任务是帮助 UltraNet 优化网络，并输出优化后网络中所有城市对之间的带宽之和。在优化以下示例时，虚线所示的三条电缆将被丢弃。在生成的网络中，瓶颈为 3，剩余四条电缆的带宽之和为 $6 + 3 + 8 + 4 = 21$，所有城市对之间的带宽之和为 $\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} b'_{i,j} = 6 + 4 + 6 + 3 + 4 + 8 + 3 + 4 + 3 + 3 = 44$。

输入格式

每个测试用例以两个整数 $n$ 和 $m$ 开头，分别表示城市和电缆的数量。接下来 $m$ 行用于指定 $m$ 条电缆。每行包含三个正整数 $i$、$j$ 和 $b_{i,j}$，表示一条带宽为 $b_{i,j}$ 的电缆直接连接城市对 $(i, j)$，其中城市编号从 $1$ 到 $n$，且由于 $b_{i,j} = b_{j,i}$，满足 $i < j$。当前网络中每对城市之间最多只有一条电缆。此外，所有电缆的带宽各不相同；没有两条电缆具有相同的带宽等级。

输出格式

输出一个整数，即优化后网络中所有城市对之间的带宽之和。

数据范围

• $2 \le n \le 10000$
• $1 \le m \le 500000$
• $1 \le i < j \le n$
• $0 < b_{i,j} < 10^7$

样例

样例输入 1

3 3
1 2 5
1 3 6
2 3 8

样例输出 1

20

样例输入 2

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

样例输出 2

44

样例输入 3

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

样例输出 3

24