题目描述

实验楼里有 $n$ 台设备和 $m$ 条连接线。每条连接线连接两台不同设备，并有一个拆除成本 $w$。最开始，所有设备通过这些连接线形成一个连通网络。

现在要把所有设备依次撤下。每次可以选择一台尚未撤下的设备 $u$，同时拆掉当前仍与 $u$ 相连的所有连接线。若这次拆掉了 $k$ 条线，成本分别为 $w_1,w_2,\ldots,w_k$，则本次操作的费用为

总费用为所有撤下操作费用之和。撤下过程中，剩余设备不要求继续保持连通。

请计算撤下全部设备的最小总费用。

输入格式

第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示设备 $u$ 和设备 $v$ 之间有一条成本为 $w$ 的连接线。

输出格式

输出一行一个整数，表示最小总费用。

样例

6 8
1 3 10
1 5 20
1 6 30
2 5 10
2 6 20
3 4 30
3 5 10
5 6 20

240

样例说明

一种最优撤下顺序为 $4,3,2,5,6,1$。对应费用依次为 $30,40,60,80,30,0$，总和为 $240$。

数据范围

• 对于 $10\%$ 的数据，所有连接线成本 $w=1$。
• 对于另外 $20\%$ 的数据，$m=n-1$。
• 对于 $100\%$ 的数据，$1\le n\le8$，$n-1\le m\le\frac{n(n-1)}{2}$，$1\le u,v\le n$，$1\le w\le10^9$。保证没有重边和自环。