The cheapest network

Choose lines from edges so that every station can reach every other, and the total cost is as small as possible: a minimum spanning tree. Return the chosen lines as a list of (u, v, w) triples, exactly as they appear in edges (either way round). Return None if the stations cannot all be joined.

edges = [(0, 1, 4), (0, 3, 2), (1, 3, 5), (1, 2, 6),
         (1, 4, 3), (3, 4, 7), (2, 4, 8), (2, 5, 1),
         (4, 5, 9), (2, 6, 5), (5, 6, 7)]
mst(7, edges)
# [(2, 5, 1), (0, 3, 2), (1, 4, 3), (0, 1, 4),
#  (2, 6, 5), (1, 2, 6)]   total 21

When several trees cost the least, any of them is accepted. The tests check that your lines are taken from the list, that there are n − 1 of them with no loop, and that their total is the least. Costs are whole numbers and may be negative. A line may join a station to itself, and two stations may be joined by more than one line.

Limits

• Up to 100,000 stations and 250,000 lines.
• Joining two groups must be fast: relabelling every station of a group each time is too slow. The big tests have 4 seconds each.