[USACO04DEC] Bad Cowtractors S
题目描述
奶牛贝茜被雇去建设 $N(2\le N\le 10^3)$ 个牛棚间的互联网。她已经勘探出 $M(1\le M\le 2\times 10^4)$ 条可建的线路,每条线路连接两个牛棚,而且会花费 $C(1\le C\le 10^5)$。农夫约翰吝啬得很,他希望建设费用最少甚至他都不想给贝茜工钱。贝茜得知工钱要告吹,决定报复。她打算选择建一些线路,把所有牛棚连接在一起,让约翰花费最大。但是她不能造出环来,这样约翰就会发现。
输入输出格式
输入格式
第 $1$ 行:$N$,$M$。
第 $2$ 到 $M+1$ 行:三个整数,表示一条可能线路的两个端点和费用。
输出格式
一行,表示最大的花费。如果不能建成合理的线路,就输出 $-1$。
输入输出样例
输入样例 #1
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17
输出样例 #1
42
说明
$2\le N\le 10^3$,$1\le M\le 2\times 10^4$,$1\le C\le 10^5$。