import math
from typing import List, Tuple, Optional, Dict

class FibonacciHeapNode:
    """Node in a Fibonacci heap."""
    
    def __init__(self, key: float, value: int):
        self.key = key
        self.value = value
        self.parent: Optional['FibonacciHeapNode'] = None
        self.child: Optional['FibonacciHeapNode'] = None
        self.left: 'FibonacciHeapNode' = self
        self.right: 'FibonacciHeapNode' = self
        self.degree = 0
        self.marked = False

class FibonacciHeap:
    """Fibonacci heap implementation for Prim's algorithm."""
    
    def __init__(self):
        self.min_node: Optional[FibonacciHeapNode] = None
        self.num_nodes = 0
        self.node_map: Dict[int, FibonacciHeapNode] = {}
    
    def is_empty(self) -> bool:
        return self.min_node is None
    
    def insert(self, key: float, value: int) -> FibonacciHeapNode:
        """Insert a new node with given key and value."""
        node = FibonacciHeapNode(key, value)
        self.node_map[value] = node
        
        if self.min_node is None:
            self.min_node = node
        else:
            self._add_to_root_list(node)
            if node.key < self.min_node.key:
                self.min_node = node
        
        self.num_nodes += 1
        return node
    
    def extract_min(self) -> Tuple[float, int]:
        """Extract and return the minimum key-value pair."""
        if self.min_node is None:
            raise ValueError("Heap is empty")
        
        min_node = self.min_node
        
        # Add all children to root list
        if min_node.child:
            child = min_node.child
            while True:
                next_child = child.right
                child.parent = None
                self._add_to_root_list(child)
                child = next_child
                if child == min_node.child:
                    break
        
        # Remove min_node from root list
        self._remove_from_root_list(min_node)
        
        if min_node == min_node.right:
            # Only node in root list
            self.min_node = None
        else:
            self.min_node = min_node.right
            self._consolidate()
        
        self.num_nodes -= 1
        del self.node_map[min_node.value]
        return min_node.key, min_node.value
    
    def decrease_key(self, value: int, new_key: float):
        """Decrease the key of the node with given value."""
        if value not in self.node_map:
            return
        
        node = self.node_map[value]
        if new_key > node.key:
            raise ValueError("New key is greater than current key")
        
        node.key = new_key
        parent = node.parent
        
        if parent and node.key < parent.key:
            self._cut(node, parent)
            self._cascading_cut(parent)
        
        if node.key < self.min_node.key:
            self.min_node = node
    
    def _add_to_root_list(self, node: FibonacciHeapNode):
        """Add node to the root list."""
        if self.min_node is None:
            self.min_node = node
            node.left = node.right = node
        else:
            node.left = self.min_node
            node.right = self.min_node.right
            self.min_node.right.left = node
            self.min_node.right = node
    
    def _remove_from_root_list(self, node: FibonacciHeapNode):
        """Remove node from the root list."""
        if node.right == node:
            return  # Only node in list
        
        node.left.right = node.right
        node.right.left = node.left
    
    def _consolidate(self):
        """Consolidate the heap by merging trees of equal degree."""
        max_degree = int(math.log(self.num_nodes) * 2) + 1
        degree_table = [None] * max_degree
        
        # Collect all root nodes
        roots = []
        current = self.min_node
        if current:
            while True:
                roots.append(current)
                current = current.right
                if current == self.min_node:
                    break
        
        # Process each root
        for root in roots:
            degree = root.degree
            while degree_table[degree] is not None:
                other = degree_table[degree]
                if root.key > other.key:
                    root, other = other, root
                
                self._heap_link(other, root)
                degree_table[degree] = None
                degree += 1
            
            degree_table[degree] = root
        
        # Find new minimum
        self.min_node = None
        for node in degree_table:
            if node is not None:
                if self.min_node is None or node.key < self.min_node.key:
                    self.min_node = node
    
    def _heap_link(self, child: FibonacciHeapNode, parent: FibonacciHeapNode):
        """Link child node under parent node."""
        self._remove_from_root_list(child)
        child.parent = parent
        
        if parent.child is None:
            parent.child = child
            child.left = child.right = child
        else:
            child.left = parent.child
            child.right = parent.child.right
            parent.child.right.left = child
            parent.child.right = child
        
        parent.degree += 1
        child.marked = False
    
    def _cut(self, child: FibonacciHeapNode, parent: FibonacciHeapNode):
        """Cut child from parent and add to root list."""
        if parent.child == child:
            if child.right == child:
                parent.child = None
            else:
                parent.child = child.right
        
        child.left.right = child.right
        child.right.left = child.left
        parent.degree -= 1
        
        child.parent = None
        child.marked = False
        self._add_to_root_list(child)
    
    def _cascading_cut(self, node: FibonacciHeapNode):
        """Perform cascading cut operation."""
        parent = node.parent
        if parent:
            if not node.marked:
                node.marked = True
            else:
                self._cut(node, parent)
                self._cascading_cut(parent)


def prim_mst_fibonacci(adj: List[List[Tuple[int, float]]]) -> List[Tuple[int, int, float]]:
    """
    Find minimum spanning tree using Prim's algorithm with Fibonacci heap.
    
    Args:
        adj: Adjacency list where adj[i] = [(j, weight), ...] 
             representing edges from vertex i to vertex j with given weight
    
    Returns:
        List of edges in MST as (u, v, weight) tuples
    """
    n = len(adj)
    if n == 0:
        return []
    
    # Initialize
    heap = FibonacciHeap()
    in_mst = [False] * n
    parent = [-1] * n
    key = [float('inf')] * n
    
    # Start with vertex 0
    start_vertex = 0
    key[start_vertex] = 0.0
    
    # Insert all vertices into heap
    for i in range(n):
        heap.insert(key[i], i)
    
    mst_edges = []
    
    while not heap.is_empty():
        # Extract minimum key vertex
        min_key, u = heap.extract_min()
        in_mst[u] = True
        
        # Add edge to MST (except for the first vertex)
        if parent[u] != -1:
            mst_edges.append((parent[u], u, min_key))
        
        # Update keys of adjacent vertices
        for v, weight in adj[u]:
            if not in_mst[v] and weight < key[v]:
                key[v] = weight
                parent[v] = u
                heap.decrease_key(v, weight)
    
    return mst_edges


# Example usage and test

# Example graph represented as adjacency list
# Graph:
#   0 -- 1 (weight 2)
#   |    |
#   |    | (weight 3)
#   |    |
#   3 -- 2 (weight 1)
#   (weight 4)

adj_matrix = [
    [(1, 2.0), (3, 4.0)],  # vertex 0 connects to 1 and 3
    [(0, 2.0), (2, 3.0)],  # vertex 1 connects to 0 and 2  
    [(1, 3.0), (3, 1.0)],  # vertex 2 connects to 1 and 3
    [(0, 4.0), (2, 1.0)]   # vertex 3 connects to 0 and 2
]

print("Adjacency list representation:")
for i, neighbors in enumerate(adj_matrix):
    print(f"Vertex {i}: {neighbors}")

print("\nFinding MST using Prim's algorithm with Fibonacci heap...")
mst = prim_mst_fibonacci(adj_matrix)

print("\nMinimum Spanning Tree edges:")
total_weight = 0
for u, v, weight in mst:
    print(f"Edge ({u}, {v}) with weight {weight}")
    total_weight += weight

print(f"\nTotal MST weight: {total_weight}")

# Test with a larger graph
print("\n" + "="*50)
print("Testing with a larger graph (5 vertices):")

large_adj = [
    [(1, 2.0), (3, 6.0)],           # 0
    [(0, 2.0), (2, 3.0), (3, 8.0), (4, 5.0)],  # 1
    [(1, 3.0), (4, 7.0)],           # 2
    [(0, 6.0), (1, 8.0), (4, 9.0)], # 3
    [(1, 5.0), (2, 7.0), (3, 9.0)]  # 4
]

mst_large = prim_mst_fibonacci(large_adj)

print("MST edges:")
total_weight_large = 0
for u, v, weight in mst_large:
    print(f"Edge ({u}, {v}) with weight {weight}")
    total_weight_large += weight

print(f"Total MST weight: {total_weight_large}")