Sgu206 Road

给定一个包含 $N$ 个顶点、$M$ 条边的无向图，其中 $M\ge N-1$。第 $i$ 条边的原权值为 $C_i$，且前 $N-1$ 条边构成一棵生成树。图中没有重边和自环。

你需要为每条边指定一个新权值 $D_i$，使前 $N-1$ 条边构成的生成树是该图的一棵最小生成树，并最小化：

$$\sum_{i=1}^{M}\lvert D_i-C_i\rvert$$

请输出该式的最小值。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行包含三个整数 $a_i,b_i,c_i$，表示一条连接顶点 $a_i$ 与顶点 $b_i$、原权值为 $c_i$ 的无向边。

输出格式

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

样例输入

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

样例输出

6

数据范围

• 对于 $30\%$ 的数据，$N\le 60$，$M\le 400$；
• 对于 $100\%$ 的数据，$N\le 1000$，$M\le 10000$；
• $M\ge N-1$。

来源与许可

本题题面与测试数据整理自 BZOJ。