정전 복구

폭풍으로 도시의 전력망이 파손되었다. 도시는 N개의 지역으로 구성되어 있으며, 지역 1에는 발전소가 있다. 각 지역 사이에는 전선을 설치할 수 있고, 설치 비용이 다르다.

모든 지역에 전기를 공급하기 위해 최소 비용으로 전선을 설치하시오.

입력

첫째 줄에 지역 수 N과 전선 수 M이 주어진다. 다음 M줄에 전선 정보 (A B C) — A지역과 B지역을 연결하는 비용 C가 주어진다.

• 2 ≤ N ≤ 1,000
• 1 ≤ M ≤ 100,000
• 1 ≤ C ≤ 10,000
• 연결 그래프가 보장된다.

출력

모든 지역에 전기를 공급하기 위한 최소 전선 설치 비용을 출력한다.

예제 입력

4 5
1 2 4
1 3 3
1 4 5
2 3 7
3 4 6

예제 출력

12