prim.py

import heapq


def iterative_minimum_spanning_tree(adj, start_node=0):
    mst = []
    visited = set()
    min_heap = [(0, start_node, -1)]  # (weight, current_node, parent_node)
    
    while min_heap:
        weight, node, parent = heapq.heappop(min_heap)
        if node in visited:
            continue
        
        visited.add(node)
        if parent != -1:
            mst.append((parent, node, weight))

        for neighbor, edge_weight in adj[node]:
            if neighbor not in visited:
                heapq.heappush(min_heap, (edge_weight, neighbor, node))

    return mst