F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1321. -- Sgu206 Road

1321: Sgu206 Road

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 71  Solved: 9
[Submit][Status][Discuss]

Description

给你一个N个点M条边的图(M >= N - 1),每条边有个权值Ci,前面N – 1条边构成一颗树,现在你需要给每条边伪造一个权值Di,使得前N– 条边构成的生成树是该图的最小生成树,并且使Sigma(Di)-Sigma(Ci)(1<=i<=M 最小。

Input

第一行两个数N, M。 接下来M行每行三个数ai,bi,ci,表示一条边,保证无重边无自环。

Output

仅一行,表示最小花费。

Sample Input

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

Sample Output

6

HINT

30%的数据,N<=60, M <= 400。
100%的数据,N<=1000, M<= 10000。

Source

[Submit][Status][Discuss]

HOME Back