네트워크 연결

도현이는 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이 된다.