크루스칼 알고리즘을 배워보자.

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html
https://techblog-history-younghunjo1.tistory.com/262

1. 가중치를 기준으로 간선을 정렬한다.
2. Union-Find 알고리즘을 이용해 Cycle 여부를 확인한다.
3. Cycle이 아니라면, 최소 스패닝 트리에 들어갈 수 있으므로 넣는다.
4. 모든 점이 연결된 이후에 연결되는 점들은 Find에 걸리므로 자동으로 없어짐

V, E = map(int, input().split())

# 부모 테이블을 초기화

parent = [i for i in range(V+1)]

# find 연산

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

# union 연산

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

# 간선 정보를 담을 리스트와 최소 신장 트리 계산 변수 정의
edges = [list(map(int, input().split())) for _ in range(E)]
total_cost = 0

edges.sort(key=lambda x: (x[2]))

# 간선 정보 하나씩 확인하면서 크루스칼 알고리즘 수행
for a, b, cost in edges:
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        total_cost += cost

print(total_cost)

Union-Find는 눈 감고 풀 수 있도록 꼭 외우자!