시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 512 MB 5030 2144 (43%) 1710
문제
S 왕국의 새로운 정부는 모든 도시를 잇는 고속도로를 건설하려 한다. 그러나 비싼 비용의 문제에 부딪혀, 정부는 최소 비용으로 모든 도시 간을 이동할 수 있게 하고 싶어한다. 또한 하나의 제약이 더 있는데, 언덕 등을 깎지 않는 친환경 건설을 위해 어떤 도시끼리는 직접 도로를 이을 수 없다. 도로 후보의 목록이 주어질 때, 정부를 도와 모든 도시 간을 잇는 고속도로를 건설하는 최소 비용을 알아내자.
입력
첫 번째 줄에 도시의 수 N이 주어진다. $(2 \le N \le 50,000)$ 두 번째 줄에 도로 후보의 수 M이 주어진다. $(1 \le M \le 200,000)$ 세 번째 줄부터 $M$개의 줄에 걸쳐 각 도로 후보의 정보 $s, e, c$가 주어진다. $s$와 $e$는 도로 후보가 잇는 각 도시의 번호이고, $c$는 그 도로를 건설하는데 드는 비용이다. $(1 \le s, e \le N, 1 \le c \le 10,000)$ 항상 모든 도시를 잇는 고속도로를 건설할 수 있는 입력만 주어진다.
출력
첫 번째 줄에 모든 도시를 잇는 고속도로를 건설하는데 드는 최소 비용을 출력한다.
힌트
#### 예제 입력 ``` 5 8 1 2 4 1 3 9 1 4 21 2 3 8 2 4 17 3 4 16 5 2 20 5 4 30 ``` #### 예제 출력 ``` 48 ```