from heapq import heappop, heappush

class Graph:

   def __init__(self, vertices):

       self.V = vertices

       self.graph = [[] for _ in range(vertices)]

   def add_edge(self, u, v, weight):

       self.graph[u].append((v, weight))

       self.graph[v].append((u, weight))

   def prim_mst(self):

       visited = [False] * self.V

       min_heap = []

       start_vertex = 0

       visited[start_vertex] = True

       for neighbor, weight in self.graph[start_vertex]:

           heappush(min_heap, (weight, start_vertex, neighbor))

       mst = []

       while min_heap:

           weight, u, v = heappop(min_heap)

           if visited[v]:

               continue

           mst.append((u, v, weight))

           visited[v] = True

           for neighbor, weight in self.graph[v]:

               if not visited[neighbor]:

                   heappush(min_heap, (weight, v, neighbor))

       return mst

class Edge:

   def __init__(self, src, dest, weight):

       self.src = src

       self.dest = dest

       self.weight = weight

class Graph:

   def __init__(self, vertices):

       self.V = vertices

       self.graph = []

   def add_edge(self, src, dest, weight):

       self.graph.append(Edge(src, dest, weight))

   def kruskal_mst(self):

       def find(parent, i):

           if parent[i] == i:

               return i

           return find(parent, parent[i])

       def union(parent, rank, x, y):

           x_root = find(parent, x)

           y_root = find(parent, y)

           if rank[x_root] < rank[y_root]:

               parent[x_root] = y_root

           elif rank[x_root] > rank[y_root]:

               parent[y_root] = x_root

           else:

               parent[y_root] = x_root

               rank[x_root] += 1

       parent = []

       rank = []

       result = []

       for node in range(self.V):

           parent.append(node)

           rank.append(0)

       i = 0

       while len(result) < self.V - 1:

           u, v, w = self.graph[i]

           i += 1

           x = find(parent, u)

           y = find(parent, v)

           if x != y:

               result.append([u, v, w])

               union(parent, rank, x, y)

       return result

g = Graph(9)

g.add_edge(0, 1, 4)

g.add_edge(0, 7, 8)

g.add_edge(1, 2, 8)

g.add_edge(1, 7, 11)

g.add_edge(2, 3, 7)

g.add_edge(2, 8, 2)

g.add_edge(2, 5, 4)

g.add_edge(3, 4, 9)

g.add_edge(3, 5, 14)

g.add_edge(4, 5, 10)

g.add_edge(5, 6, 2)

g.add_edge(6, 7, 1)

g.add_edge(6, 8, 6)

g.add_edge(7, 8, 7)

mst_prim = g.prim_mst()

m