import heapq

def prim(graph):
    """
    Finds the Minimum Spanning Tree (MST) of a connected, undirected,
    weighted graph using Prim's algorithm.

    Args:
        graph (dict): An adjacency list representation of the graph.
                      {vertex: [(neighbor, weight), ...]}

    Returns:
        tuple: A tuple containing:
               - list: The edges forming the MST, e.g., [(u, v, weight), ...]
               - int: The total weight of the MST.
    """
    if not graph:
        return [], 0

    vertices = list(graph.keys())
    if not vertices:
        return [], 0

    # Start with an arbitrary vertex (e.g., the first one in the list)
    start_node = vertices[0]
    
    # Set to keep track of vertices already included in the MST
    in_mst = {start_node}
    
    # Priority queue to store edges (weight, u, v)
    # The edge (u, v) connects a vertex u IN the MST to a vertex v NOT IN the MST.
    min_heap = []

    # Add all edges connected to the start_node to the priority queue
    # This also handles cases where a neighbor might not be a direct key in graph (isolated node scenarios),
    # though for connected graphs used here, all vertices will be keys.
    for neighbor, weight in graph.get(start_node, []):
        heapq.heappush(min_heap, (weight, start_node, neighbor))

    mst_edges = []
    mst_weight = 0

    # Continue until all vertices are included in the MST
    # An MST for a graph with |V| vertices has |V|-1 edges.
    while min_heap and len(in_mst) < len(vertices):
        weight, u, v = heapq.heappop(min_heap)

        # If 'v' is already in the MST, this edge forms a cycle, so skip it
        if v in in_mst:
            continue

        # Add the edge to the MST
        mst_edges.append((u, v, weight))
        mst_weight += weight
        
        # Add 'v' to the set of vertices in the MST
        in_mst.add(v)

        # Now, add all edges connected to the newly added vertex 'v'
        # that lead to vertices NOT YET in the MST
        for neighbor_of_v, weight_of_edge in graph.get(v, []):
            if neighbor_of_v not in in_mst:
                heapq.heappush(min_heap, (weight_of_edge, v, neighbor_of_v))
    
    # Check if all vertices were connected. If not, the graph was not connected.
    if len(in_mst) < len(vertices):
        print("Warning: The graph is not connected. MST cannot include all vertices from the original graph.")
        # For a truly disconnected graph, this implementation finds an MST of the connected component
        # containing the start_node. It won't find a spanning tree for the whole graph.
        return [], 0 

    return mst_edges, mst_weight

# --- Example Usage ---
# Graph represented as an adjacency list (from CLRS, Fig 23.4, "MST-PRIM"):
# {node: [(neighbor1, weight1), (neighbor2, weight2), ...]}
# Note: For an undirected graph, if (u,v,w) exists, (v,u,w) must also be present.
graph_prim_example = {
    'A': [('B', 4), ('H', 8)],
    'B': [('A', 4), ('C', 8), ('H', 11)],
    'C': [('B', 8), ('D', 7), ('F', 4), ('I', 2)],
    'D': [('C', 7), ('E', 9), ('F', 14)],
    'E': [('D', 9), ('F', 10)],
    'F': [('C', 4), ('D', 14), ('E', 10), ('G', 2)],
    'G': [('F', 2), ('H', 1), ('I', 6)],
    'H': [('A', 8), ('B', 11), ('G', 1), ('I', 7)],
    'I': [('C', 2), ('G', 6), ('H', 7)]
}

mst_prim_edges, total_prim_weight = prim(graph_prim_example)

print("--- Prim's Algorithm ---")
print("MST Edges:")
for u, v, w in mst_prim_edges:
    print(f"  Edge: ({u}-{v}), Weight: {w}")
print(f"Total MST Weight: {total_prim_weight}")

# Another example: A simpler graph
simple_graph_prim = {
    'A': [('B', 1), ('C', 3)],
    'B': [('A', 1), ('C', 1), ('D', 5)],
    'C': [('A', 3), ('B', 1), ('D', 2)],
    'D': [('B', 5), ('C', 2)]
}

mst_simple_prim_edges, total_simple_prim_weight = prim(simple_graph_prim)

print("\n--- Prim's Algorithm (Simple Graph) ---")
print("MST Edges:")
for u, v, w in mst_simple_prim_edges:
    print(f"  Edge: ({u}-{v}), Weight: {w}")
print(f"Total MST Weight: {total_simple_prim_weight}")

class DisjointSetUnion:
    """
    A simple Disjoint Set Union (DSU) data structure with path compression
    and union by size for efficient `find` and `union` operations.
    """
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.size = {v: 1 for v in vertices} # For union by size

    def find(self, i):
        """
        Finds the representative (root) of the set containing element 'i'.
        Applies path compression.
        """
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i]) # Path compression
        return self.parent[i]

    def union(self, i, j):
        """
        Unites the sets containing elements 'i' and 'j'.
        Applies union by size. Returns True if union happened, False if already in same set.
        """
        root_i = self.find(i)
        root_j = self.find(j)

        if root_i != root_j:
            # Union by size: attach smaller tree under root of larger tree
            if self.size[root_i] < self.size[root_j]:
                self.parent[root_i] = root_j
                self.size[root_j] += self.size[root_i]
            else:
                self.parent[root_j] = root_i
                self.size[root_i] += self.size[root_j]
            return True # Union successful
        return False # Already in the same set

def kruskal(graph_edges, num_vertices):
    """
    Finds the Minimum Spanning Tree (MST) of a connected, undirected,
    weighted graph using Kruskal's algorithm.

    Args:
        graph_edges (list): A list of edges, where each edge is
                            (u, v, weight).
        num_vertices (int): The total number of vertices in the graph.
                            This is used to know when enough edges are added.

    Returns:
        tuple: A tuple containing:
               - list: The edges forming the MST, e.g., [(u, v, weight), ...]
               - int: The total weight of the MST.
    """
    if not graph_edges and num_vertices == 0:
        return [], 0
    if num_vertices <= 1: # An MST of 0 or 1 vertex is an empty graph or the vertex itself
        return [], 0

    # Sort all edges by weight in non-decreasing order
    # Note: Python's sorted() is stable, but for elements with equal weight, 
    # the relative order might vary depending on Python version/implementation details.
    # This can lead to different valid MSTs if edge weights are not unique, but the total weight will be the same.
    sorted_edges = sorted(graph_edges, key=lambda x: x[2])

    # Initialize DSU structure with all unique vertices found in the edges
    all_vertices = set()
    for u, v, _ in graph_edges:
        all_vertices.add(u)
        all_vertices.add(v)
    
    # It's important to initialize DSU for ALL vertices in the graph,
    # including potential isolated ones, if `num_vertices` includes them.
    # Here, we assume `all_vertices` captures all relevant vertices for connectivity.
    dsu = DisjointSetUnion(all_vertices)

    mst_edges = []
    mst_weight = 0
    edges_count = 0

    # Iterate through sorted edges
    for u, v, weight in sorted_edges:
        # If adding this edge does not form a cycle (i.e., u and v are in different components)
        if dsu.union(u, v):
            mst_edges.append((u, v, weight))
            mst_weight += weight
            edges_count += 1
            
            # An MST has exactly |V|-1 edges. Once we have enough, we're done.
            if edges_count == num_vertices - 1:
                break
    
    # Check if all vertices were connected. If the graph was connected, 
    # edges_count should be num_vertices - 1.
    if edges_count < num_vertices - 1:
        print("Warning: The graph is not connected. MST cannot include all vertices.")
        # If the graph has isolated vertices not part of any edge, 
        # num_vertices - 1 might be larger than actual edges_count for the connected components.
        # For a disconnected graph, Kruskal's will find a Minimum Spanning Forest (MSF).
        # We can still return the MST of the largest component found.
            
    return mst_edges, mst_weight

# --- Example Usage ---
# Graph represented as a list of edges: (u, v, weight)
# Vertices are A, B, C, D, E, F, G, H, I (9 vertices)
graph_kruskal_edges = [
    ('A', 'B', 4), ('A', 'H', 8),
    ('B', 'C', 8), ('B', 'H', 11),
    ('C', 'D', 7), ('C', 'F', 4), ('C', 'I', 2),
    ('D', 'E', 9), ('D', 'F', 14),
    ('E', 'F', 10),
    ('F', 'G', 2),
    ('G', 'H', 1), ('G', 'I', 6),
    ('H', 'I', 7)
]
num_vertices_kruskal = 9 # A, B, C, D, E, F, G, H, I

mst_kruskal_edges, total_kruskal_weight = kruskal(graph_kruskal_edges, num_vertices_kruskal)

print("\n--- Kruskal's Algorithm ---")
print("MST Edges:")
for u, v, w in mst_kruskal_edges:
    print(f"  Edge: ({u}-{v}), Weight: {w}")
print(f"Total MST Weight: {total_kruskal_weight}")

# Another example: A simpler graph
# Vertices are A, B, C, D (4 vertices)
simple_graph_kruskal = [
    ('A', 'B', 1), ('A', 'C', 3),
    ('B', 'C', 1), ('B', 'D', 5),
    ('C', 'D', 2)
]
num_vertices_simple_kruskal = 4

mst_simple_kruskal_edges, total_simple_kruskal_weight = kruskal(simple_graph_kruskal, num_vertices_simple_kruskal)

print("\n--- Kruskal's Algorithm (Simple Graph) ---")
print("MST Edges:")
for u, v, w in mst_simple_kruskal_edges:
    print(f"  Edge: ({u}-{v}), Weight: {w}")
print(f"Total MST Weight: {total_simple_kruskal_weight}")