마을 N개를 도로로 전부 연결하려고 해요. 놓을 수 있는 도로 후보 M개와 각 공사비가 주어질 때, 모든 마을이 연결되는 최소 공사비를 구하세요.
입력
첫째 줄에 N과 M이 주어져요. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 5,000) 다음 M줄에 u v w(마을 u와 v를 잇는 비용 w)가 주어져요. (1 ≤ w ≤ 1,000, 전부 연결하는 방법은 항상 있어요)
출력
최소 공사비를 출력해요.
마을 N개를 도로로 전부 연결하려고 해요. 놓을 수 있는 도로 후보 M개와 각 공사비가 주어질 때, 모든 마을이 연결되는 최소 공사비를 구하세요.
첫째 줄에 N과 M이 주어져요. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 5,000) 다음 M줄에 u v w(마을 u와 v를 잇는 비용 w)가 주어져요. (1 ≤ w ≤ 1,000, 전부 연결하는 방법은 항상 있어요)
최소 공사비를 출력해요.
3 3 1 2 1 2 3 2 1 3 3
3
로그인하면 제출할 수 있어요.