61. Minimum Cost to Connect All Nodes

Difficulty: hard · Greedy, Sorting

Problem

A network has `V` nodes numbered `1` to `V` and `E` possible undirected links. Each link connects two nodes and has a cost. Choose links so that every node is connected to every other (directly or indirectly) at minimum total cost, i.e. find the cost of a minimum spanning tree. If it is impossible to connect all nodes, print `-1`.

Input

- Line 1: two integers `V` and `E`. - Next `E` lines: three integers `u v w`, a link between nodes `u` and `v` with cost `w`.

Output

Print the minimum total cost, or `-1` if the graph cannot be connected.

Example 1

Input:
4 5
1 2 1
2 3 4
1 3 3
3 4 2
2 4 5
Output:
6

Explanation: Take links 1-2 (1), 3-4 (2) and 1-3 (3): all four nodes are connected for 1 + 2 + 3 = 6.

Example 2

Input:
3 1
1 2 7
Output:
-1

Explanation: Node 3 has no links, so the network cannot be connected.

Constraints

- 1 <= V <= 10^4 - 0 <= E <= 10^5 - 1 <= u, v <= V (self-loops and repeated links may appear) - 0 <= w <= 10^6

Solutions are judged against 2 sample and 10 hidden tests. Sign in to solve it · All problems