import sys
 
def prims_algorithm(graph):
    num_vertices = len(graph)
    selected = [False] * num_vertices
    selected[0] = True  # Start from the first vertex
 
    edges = []
    total_weight = 0
 
    for _ in range(num_vertices - 1):
        min_edge = (sys.maxsize, None, None)  # (weight, start_vertex, end_vertex)
 
        for start in range(num_vertices):
            if selected[start]:
                for end in range(num_vertices):
                    if not selected[end] and graph[start][end]:
                        if graph[start][end] < min_edge[0]:
                            min_edge = (graph[start][end], start, end)
 
        weight, start_vertex, end_vertex = min_edge
        edges.append((start_vertex, end_vertex, weight))
        total_weight += weight
        selected[end_vertex] = True
 
    return total_weight, edges
 
# Example usage
graph = [
    [0, 4, 3, 0],
    [4, 0, 1, 2],
    [3, 1, 0, 4],
    [0, 2, 4, 0]
]
 
total_weight, mst_edges = prims_algorithm(graph)
print(f"Total weight of MST: {total_weight}")
print("Edges in the MST:")
for edge in mst_edges:
    print(f"{edge[0]} -- {edge[1]} with weight {edge[2]}")
 
 

aW1wb3J0IHN5cwoKZGVmIHByaW1zX2FsZ29yaXRobShncmFwaCk6CiAgICBudW1fdmVydGljZXMgPSBsZW4oZ3JhcGgpCiAgICBzZWxlY3RlZCA9IFtGYWxzZV0gKiBudW1fdmVydGljZXMKICAgIHNlbGVjdGVkWzBdID0gVHJ1ZSAgIyBTdGFydCBmcm9tIHRoZSBmaXJzdCB2ZXJ0ZXgKCiAgICBlZGdlcyA9IFtdCiAgICB0b3RhbF93ZWlnaHQgPSAwCgogICAgZm9yIF8gaW4gcmFuZ2UobnVtX3ZlcnRpY2VzIC0gMSk6CiAgICAgICAgbWluX2VkZ2UgPSAoc3lzLm1heHNpemUsIE5vbmUsIE5vbmUpICAjICh3ZWlnaHQsIHN0YXJ0X3ZlcnRleCwgZW5kX3ZlcnRleCkKCiAgICAgICAgZm9yIHN0YXJ0IGluIHJhbmdlKG51bV92ZXJ0aWNlcyk6CiAgICAgICAgICAgIGlmIHNlbGVjdGVkW3N0YXJ0XToKICAgICAgICAgICAgICAgIGZvciBlbmQgaW4gcmFuZ2UobnVtX3ZlcnRpY2VzKToKICAgICAgICAgICAgICAgICAgICBpZiBub3Qgc2VsZWN0ZWRbZW5kXSBhbmQgZ3JhcGhbc3RhcnRdW2VuZF06CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIGdyYXBoW3N0YXJ0XVtlbmRdIDwgbWluX2VkZ2VbMF06CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBtaW5fZWRnZSA9IChncmFwaFtzdGFydF1bZW5kXSwgc3RhcnQsIGVuZCkKCiAgICAgICAgd2VpZ2h0LCBzdGFydF92ZXJ0ZXgsIGVuZF92ZXJ0ZXggPSBtaW5fZWRnZQogICAgICAgIGVkZ2VzLmFwcGVuZCgoc3RhcnRfdmVydGV4LCBlbmRfdmVydGV4LCB3ZWlnaHQpKQogICAgICAgIHRvdGFsX3dlaWdodCArPSB3ZWlnaHQKICAgICAgICBzZWxlY3RlZFtlbmRfdmVydGV4XSA9IFRydWUKCiAgICByZXR1cm4gdG90YWxfd2VpZ2h0LCBlZGdlcwoKIyBFeGFtcGxlIHVzYWdlCmdyYXBoID0gWwogICAgWzAsIDQsIDMsIDBdLAogICAgWzQsIDAsIDEsIDJdLAogICAgWzMsIDEsIDAsIDRdLAogICAgWzAsIDIsIDQsIDBdCl0KCnRvdGFsX3dlaWdodCwgbXN0X2VkZ2VzID0gcHJpbXNfYWxnb3JpdGhtKGdyYXBoKQpwcmludChmIlRvdGFsIHdlaWdodCBvZiBNU1Q6IHt0b3RhbF93ZWlnaHR9IikKcHJpbnQoIkVkZ2VzIGluIHRoZSBNU1Q6IikKZm9yIGVkZ2UgaW4gbXN0X2VkZ2VzOgogICAgcHJpbnQoZiJ7ZWRnZVswXX0gLS0ge2VkZ2VbMV19IHdpdGggd2VpZ2h0IHtlZGdlWzJdfSIpCgo=