Description

Bessie the cow was hired to build the internet among $N$ ($2 \le N \le 10^3$) barns. She has surveyed $M$ ($1 \le M \le 2 \times 10^4$) buildable links; each link connects two barns and costs $C$ ($1 \le C \le 10^5$). Farmer John is very stingy; he wants the total cost minimized, and he does not even want to pay Bessie. Learning that her pay will be canceled, Bessie decides to retaliate. She plans to choose some links to connect all barns together, making John pay as much as possible. However, she cannot create cycles; otherwise John would notice.

Input Format

Line $1$: $N$, $M$.

Lines $2$ to $M + 1$: three integers, the two endpoints of a possible link and its cost.

Output Format

One line, the maximum possible total cost. If it is impossible to form a valid set of links, output $-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

Hint

Constraints: $2 \le N \le 10^3$, $1 \le M \le 2 \times 10^4$, $1 \le C \le 10^5$.

Translated by ChatGPT 5