There are n cities numbered 1..n and a list of broken two-way roads. Each road is a tuple (a, b, cost): repairing it costs cost. Choose roads to repair so that every city can reach every other city, spending as little as possible.
Implement road_reparation(n: int, roads: list[tuple[int, int, int]]) -> int | None: return the minimum total cost, or None if no choice of roads connects all the cities.
road_reparation(4, [(1, 2, 4), (2, 3, 1), (1, 3, 2), (3, 4, 7), (2, 4, 9)]) # 10 (2 + 1 + 7)
road_reparation(3, [(1, 2, 5)]) # None (city 3 is cut off)
road_reparation(1, []) # 0
Constraints: 1 <= n <= 10^5, up to 2 * 10^5 roads, 1 <= cost <= 10^9. Roads may repeat a pair of cities, and a road may connect a city to itself.
Aim for O(m log m) for m roads.
Show hint
consider roads from cheapest to most expensive and repair one only if it joins two cities that aren't connected yet. A structure that tracks which cities are already connected makes each check fast.