386. Prim's Algorithm - MST Edges

Given a connected undirected weighted graph with n vertices (0-indexed) and m edges (each u, v, weight), run Prim's algorithm starting from vertex 0: at every step, among all edges connecting a tree vertex to a non-tree vertex, add the one with the smallest weight (ties broken by the smaller non-tree endpoint, then the smaller tree endpoint). Print each added edge as 'u v' (tree endpoint first), in the order Prim's algorithm adds them, followed by a final line with the total weight of the spanning tree.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains three integers u v w, an undirected weighted edge. Output: Print each edge Prim's algorithm adds as 'u v' (tree endpoint first) in the order added, one per line, followed by a final line with the total spanning tree weight.

1 <= n <= 10^5

The specific tuple ordering (weight, non-tree vertex, tree vertex) is exactly what gives the DETERMINISTIC tie-breaking this problem requires - Python's/JS's natural tuple/array comparison (or a custom comparator matching this order) handles the tie-break rule 'for free' without extra logic.

Grow a minimum spanning tree from a starting vertex, adding the cheapest connecting edge at every step, and print exactly which edges get added. Brute force: Try every possible order of adding edges and check which produces a valid minimum spanning tree - this is combinatorially expensive, when the heap-based greedy directly produces the correct edges in the correct order. Optimised: A min-heap of candidate boundary-crossing edges, with STALE entries simply discarded when popped (rather than proactively removed), avoids the complexity of maintaining a perfectly up-to-date heap - since a vertex, once added to the tree, will never usefully be revisited, any leftover heap entries pointing to it can just be safely ignored when encountered.

Build an adjacency list and use a binary-heap-backed priority queue keyed on edge weight: push the start vertex's edges, repeatedly pop the minimum-weight edge that leads to a still-unvisited vertex, add it to the MST, and push all edges from the newly added vertex. Because the heap always hands back the globally smallest available edge in O(log n), this avoids scanning every vertex at every step, which is a big win on sparse graphs where the number of edges m is much less than n^2. Time: O((n + m) log n) Space: O(n + m)

Maintain a key[] array holding the cheapest known edge weight connecting each non-tree vertex to the growing MST, initialised to infinity except the start vertex. At each of the n steps, scan all n vertices linearly to find the closest non-tree vertex, add the corresponding edge, then update key[] for its neighbours. This is the textbook 'naive' Prim's algorithm: it's correct and simple, and actually performs well on dense graphs, but the repeated linear scans make it scale quadratically with the vertex count. Time: O(n^2) Space: O(n)

Use an indexed priority queue (conceptually a Fibonacci heap) that supports true decrease-key: rather than pushing a fresh heap entry every time an edge relaxes a vertex's key (which the plain binary-heap version does, inflating the heap size to O(m)), update that vertex's existing entry in place. Decrease-key on this structure runs in amortised O(1), while extract-min stays O(log n), so the total work becomes proportional to edges plus one log factor per vertex rather than per edge. This is the asymptotically best known comparison-based bound for Prim's algorithm. Time: O(m + n log n) Space: O(n + m)

1. Keep a min-heap of candidate edges (weight, non-tree-endpoint, tree-endpoint) crossing the tree's current boundary; push a vertex's edges onto it the moment that vertex JOINS the tree. 2. Pop the heap until finding an edge whose non-tree endpoint HASN'T already joined the tree (stale entries for already-added vertices are simply discarded, not acted on). 3. The heap's natural tuple ordering (weight, then non-tree vertex, then tree vertex) already gives the exact deterministic tie-break this problem requires.

Time: O(m log m) - each edge can be pushed onto the heap at most once per endpoint, and each pop/push is O(log m). Space: O(m), for the heap holding candidate edges.

Test n = 1 (no edges added, total weight 0), ties in edge weight requiring the specified tie-break (smaller non-tree endpoint, then smaller tree endpoint), and n at the upper bound of 10^5.

Be ready to explain the 'lazy deletion' pattern here (letting stale heap entries simply be discarded when popped, rather than actively removing them when they become stale) - a broadly reusable heap technique whenever entries can become outdated over time.