Take an optimum that lacks that edge. Adding it creates a cycle; the cycle contains another edge crossing the same inside/outside cut. Replace that edge with the no-more-expensive chosen one. Connectivity remains and total cost does not increase.

The heap stores edges from included vertices toward possible new vertices. Pop the cheapest offer; skip it if its endpoint is already inside. Otherwise include that endpoint, add the edge weight to the total, and offer its outgoing edges. This is not Dijkstra: no accumulated source-to-vertex route cost appears in the key. Negative edge weights are fine for MST cut reasoning. If the queue empties before all vertices join, no spanning tree exists.

What the function promises: n vertices and weighted undirected edges use labels 0..n−1. Return (minimum total weight, selected edges), or None for a disconnected graph. Empty input returns (0, []).

from heapq import heappop, heappush

def prim_tree(n, edges):
    if n == 0:
        return 0, []
    graph = [[] for _ in range(n)]
    for u, v, weight in edges:
        graph[u].append((v, weight))
        graph[v].append((u, weight))
    heap = [(0, 0, -1)]
    inside, chosen, total = set(), [], 0
    while heap:
        weight, u, parent = heappop(heap)
        if u in inside:
            continue
        inside.add(u)
        total += weight
        if parent != -1:
            chosen.append((parent, u, weight))
        for v, edge_weight in graph[u]:
            if v not in inside:
                heappush(heap, (edge_weight, v, u))
    return (total, chosen) if len(inside) == n else None

assert prim_tree(3, [(0,1,1), (0,2,4), (1,2,2)])[0] == 3
assert prim_tree(2, [(0,1,-2)])[0] == -2
assert prim_tree(3, [(0,1,1)]) is None

Work and storage: O(V+E log(E+2)) time and O(V+E) storage for this lazy edge-heap implementation. For simple connected graphs this is customarily written O(E log V).

When to recognize it: Grow one connected set. Choose its cheapest edge crossing to a new vertex.

Check before applying it: Prim’s key is a single connecting edge, not a whole route distance. Do not substitute it for Dijkstra.

Yes. Edges AB=2, AC=2, BC=1 give shortest routes from A using AB and AC, total 4. An MST uses BC plus either edge from A, total 3, but one source route becomes length 3 instead of 2.