연결이 될까

첫 줄에 노드의 개수 n (1 이상 100000 이하) 과 간선의 개수 m (0 이상 4000 이하) 이 주어집니다. 이어서 m개의 줄에 간선 u v w 가 주어집니다. w 는 그 간선의 비용(1 이상 1000000 이하)입니다.

모든 노드를 잇는 최소 비용을 출력하세요. 모두 잇는 것이 불가능하면 -1 을 출력합니다.

예시

입력

4 5
1 2 1
2 3 2
1 3 3
3 4 4
2 4 5

출력

7