Cheapest Cable Network

A village has n houses, numbered 0 to n - 1, and wants all of them on one internet network. options lists the cables that could be laid: [a, b, cost] connects houses a and b, in both directions, for cost coins. Two houses are connected if a chain of laid cables links them, directly or through other houses.

Write cheapest_network(n, options) that returns the smallest total cost of a set of cables that connects every house to every other house, or -1 if the available cables can never connect them all.

Examples

options = [[0, 1, 1], [1, 2, 4], [2, 3, 2], [0, 3, 7], [0, 2, 3]]
cheapest_network(4, options)  # returns 6
cheapest_network(3, [[0, 1, 5]])  # returns -1
cheapest_network(1, [])  # returns 0

In the first village the cables 0-1 (1 coin), 2-3 (2 coins) and 0-2 (3 coins) connect all four houses for 6 coins, and no other choice is cheaper. In the second, no cable reaches house 2.

Constraints

• 1 <= n <= 1000, with up to 5,000 options.
• 0 <= cost <= 1,000,000. Two houses can have several cable options between them.