Sgu206 Road
时间限制：5s 空间限制：162MB
题目描述
给你一个N个点M条边的图(M >= N - 1)，每条边有个权值Ci，前面N – 1条边构成一颗树，现在你需要给每条边伪造一个权值Di，使得前N– 条边构成的生成树是该图的最小生成树，并且使Sigma(Di)-Sigma(Ci)(1<=i<=M 最小。
输入格式
第一行两个数N, M。 接下来M行每行三个数ai,bi,ci，表示一条边，保证无重边无自环。
输出格式
仅一行，表示最小花费。
样例输入
4 5 4 1 7 2 1 5 3 4 4 4 2 5 1 3 1
样例输出
6
提示
30%的数据，N<=60, M <= 400。 100%的数据，N<=1000, M<= 10000。
题目来源
没有写明来源