题目描述

给你一个 $N$ 个点 $M$ 条边的图( $M \geq N - 1$)，每条边有个权值 $C_i$，前面 $N – 1$ 条边构成一颗树，现在你需要给每条边构造一个新权值 $D_i$，使得前 $N–1$ 条边构成的生成树是该图的最小生成树，并且使

最小。

输入格式

第一行两个数 $N, M$。 接下来M行每行三个数 $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\leq60, M \leq400$。

100%的数据，$N\leq1000, M\leq 10000$。