impo
 
rt heapq


class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = {}

    def add_edge(self, u, v, w):
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append((v, w))
        self.graph[v].append((u, w))

    def primMST(self):
        visited = [False] * self.V
        edges = []
        for vertex in range(self.V):
            if not visited[vertex]:
                visited[vertex] = True
                edges.append((0, vertex, -1))
            for neighbor, weight in self.graph[vertex]:
                if not visited[neighbor]:
                    edges.append((weight, vertex, neighbor))
        edges = sorted(edges)  # 按权重从小到大排序
        mst = []
        for edge in edges:
            cost, frm, to = edge
            if to == -1:  # 如果是起始节点，跳过
                continue
            mst.append((frm, to, cost))
            visited[to] = True
            for next_neighbor, next_weight in self.graph[to]:  # 更新邻居节点的最小距离
                if next_neighbor not in visited and next_weight < edges[0][0]:  # 如果邻居节点未访问且距离更短
                    heapq.heappop(edges)  # 从堆中删除当前最小距离的边
                    heapq.heappush(edges, (next_weight, to, next_neighbor))  # 添加新的最小距离的边到堆中
        return mst
g = Graph(4)
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 3)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 2)
g.add_edge(2, 3, 4)
a=g.primMST()
print(a)#[(1, 2, 1), (0, 1, 2), (1, 3, 2), (0, 2, 3), (2, 3, 4)]