A minimum spanning tree (MST) connects all n nodes of an undirected weighted graph using n - 1 edges of the smallest possible total weight. Prim's algorithm grows the tree from one node: repeatedly take the cheapest edge that leaves the tree and add the node at its other end.
Nodes are 0 .. n-1 and edges is a list of undirected (a, b, w). Implement prim_mst(n, edges) -> int | None: the total weight of an MST, or None if the graph is disconnected (no spanning tree exists).
prim_mst(4, [(0, 1, 1), (1, 2, 4), (0, 2, 3), (2, 3, 2), (1, 3, 6)]) # 6 (1 + 3 + 2)
prim_mst(3, [(0, 1, 5)]) # None (node 2 is cut off)
prim_mst(1, []) # 0
Constraints: 1 <= n <= 5 * 10^4, up to 2 * 10^5 edges, -10^6 <= w <= 10^6 (negative weights are fine for an MST). Edges may repeat a pair, and self-loops may appear.
Use Prim with heapq, starting from node 0 (Kruskal gives the same answer, but practise Prim here).
Show hint
keep a heap of (weight, node) for edges leaving the tree; when you pop a node that is already in the tree, skip it, otherwise add its weight and push all its edges.