네트워크 연결
면접 대비시간 제한2초메모리 제한256 MB
컴퓨터 N개와 비용이 있는 연결 M개가 주어질 때 모든 컴퓨터를 하나로 연결하는 최소 비용(최소 스패닝 트리)을 구합니다.
문제
도현이는 N대의 컴퓨터를 하나의 네트워크로 모두 연결하려고 한다. 별도의 허브가 없으므로 두 컴퓨터를 직접 연결하는 선을 선택해야 한다.
두 컴퓨터 사이에 직접 연결선이 있거나, 여러 연결선을 거쳐 이동할 수 있는 경로가 있으면 두 컴퓨터는 연결되어 있다고 본다.
각 연결선마다 설치 비용이 주어진다. 모든 컴퓨터가 서로 연결되도록 선을 골랐을 때 필요한 최소 비용을 구하라. 모든 컴퓨터를 연결할 수 있는 입력만 주어진다.
입력
첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)이 주어진다.
둘째 줄에 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)이 주어진다.
다음 M개의 줄에는 세 정수 a, b, c가 주어진다. 이는 컴퓨터 a와 컴퓨터 b를 직접 연결하는 비용이 c (1 ≤ c ≤ 10,000)임을 뜻한다. a와 b가 같을 수도 있다.
출력
모든 컴퓨터를 하나의 네트워크로 연결하는 데 필요한 최소 비용을 첫째 줄에 출력한다.
힌트
공개 예시에서는 1-3, 2-3, 3-4, 4-5, 4-6 연결을 선택하면 최소 비용 23이 된다.