A telecom company wants to lay cables between n hubs, numbered 0 to n - 1, so that
every hub can communicate with every other hub (directly or through other hubs). There are m
candidate two-way cable routes; route i connects hubs u and v at a build cost of w. Multiple
candidate routes between the same pair of hubs may be offered, at different costs.
Print the minimum total cost of a set of cables that connects all n hubs into a single network. If
it is impossible to connect all hubs no matter which cables are chosen, print -1 instead.
Input format
Line 1: two integers n m.
Next m lines: three integers u v w -- an undirected candidate cable between hubs u and v
costing w to build (hubs are 0-indexed).
Output format
A single integer: the minimum total build cost to connect all hubs, or -1 if it is impossible.
Constraints
- 1 <= n <= 1000
- 0 <= m <= 4000
- 0 <= u, v < n, u != v
- 1 <= w <= 1000