Bad Cowtractors

Bessie has been hired to build a cheap internet network among Farmer John's $N$ ($2 \le N \le 1{,}000$) barns, conveniently numbered $1 \ldots N$. Farmer John has already done some surveying and found $M$ ($1 \le M \le 20{,}000$) possible connection routes between pairs of barns. Each possible connection route has an associated cost $C$ ($1 \le C \le 100{,}000$). Farmer John wants to spend as little as possible on connecting the network; he does not even want to pay Bessie.

Realizing that Farmer John will not pay her, Bessie decides to do the worst job possible. She must choose a set of connections to install so that:

1. the total cost of these connections is as large as possible;
2. all the barns are connected together (it is possible to reach any barn from any other barn via a path of installed connections); and
3. there are no cycles among the connections (which Farmer John would easily detect).

Conditions 2 and 3 ensure that the final set of connections forms a tree.

• Line 1: Two space-separated integers, $N$ and $M$.
• Lines $2 \ldots M+1$: Each line contains three space-separated integers $A$, $B$, and $C$, describing a connection route between barns $A$ and $B$ with cost $C$.

• Line 1: A single integer: the largest possible total cost of a set of connections that forms a spanning tree of all the barns. If it is impossible to connect all the barns, output $-1$ instead.