#P1669. [USACO04DEC] Bad Cowtractors S

[USACO04DEC] Bad Cowtractors S

题目描述

奶牛贝茜被雇去建设 N(2N103)N(2\le N\le 10^3) 个牛棚间的互联网。她已经勘探出 M(1M2×104)M(1\le M\le 2\times 10^4) 条可建的线路,每条线路连接两个牛棚,而且会花费 C(1C105)C(1\le C\le 10^5)。农夫约翰吝啬得很,他希望建设费用最少甚至他都不想给贝茜工钱。贝茜得知工钱要告吹,决定报复。她打算选择建一些线路,把所有牛棚连接在一起,让约翰花费最大。但是她不能造出环来,这样约翰就会发现。

输入格式

11 行:NNMM

22M+1M+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
42

提示

2N1032\le N\le 10^31M2×1041\le M\le 2\times 10^41C1051\le C\le 10^5