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$ 的无向边。

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

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