"""Guided lab: monitor roads, then buy a minimum-cost repair set."""


class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n
        self.largest = 1 if n else 0

    def find(self, node):
        while node != self.parent[node]:
            self.parent[node] = self.parent[self.parent[node]]
            node = self.parent[node]
        return node

    def union(self, first, second):
        first, second = self.find(first), self.find(second)
        if first == second:
            return False
        if self.size[first] < self.size[second]:
            first, second = second, first
        self.parent[second] = first
        self.size[first] += self.size[second]
        self.components -= 1
        self.largest = max(self.largest, self.size[first])
        return True


def road_repair(n, existing, candidates):
    if n <= 0:
        raise ValueError("At least one village is required")
    for first, second in existing:
        if not 0 <= first < n or not 0 <= second < n:
            raise ValueError("Unknown village")
    for first, second, cost in candidates:
        if not 0 <= first < n or not 0 <= second < n or cost < 0:
            raise ValueError("Unknown village or negative repair cost")
    groups, history = DisjointSet(n), []
    for first, second in existing:
        changed = groups.union(first, second)
        history.append({"joined": changed, "components": groups.components,
                        "largest": groups.largest})
    repairs, cost = [], 0
    # Undirected endpoints are normalized to make equal-cost choices stable.
    proposals = sorted((price, min(a, b), max(a, b)) for a, b, price in candidates)
    for price, first, second in proposals:
        if groups.union(first, second):
            repairs.append((first, second, price))
            cost += price
    clusters = {}
    for village in range(n):
        clusters.setdefault(groups.find(village), []).append(village)
    possible = groups.components == 1
    return {"history": history, "possible": possible,
            "cost": cost if possible else None, "repairs": repairs,
            "clusters": sorted(clusters.values(), key=lambda group: group[0])}