최소 신장 트리 (MST)

문제 설명

N개의 정점과 M개의 가중치 간선이 있는 그래프에서 최소 신장 트리의 가중치 합을 구하세요.

입력 형식

첫 줄: 정점 수 N, 간선 수 M

다음 M줄: 정점1 정점2 가중치

출력 형식

MST 가중치 합

크루스칼 알고리즘

1. 간선을 가중치 순으로 정렬
2. 가장 작은 간선부터 선택
3. 사이클이 생기지 않으면 추가 (Union-Find)
4. N-1개 간선 선택 시 종료