You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

奶牛贝茜被雇去建设 $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$。

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

提示

$2\le N\le 10^3$，$1\le M\le 2\times 10^4$，$1\le C\le 10^5$。