두 그룹으로 나누기

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

모든 노드를 이은 뒤, 노드들을 정확히 두 그룹으로 나누려고 합니다. 두 그룹 사이의 연결은 끊어도 됩니다. 이때 유지해야 하는 간선 비용의 최솟값을 출력하세요. 입력 그래프는 항상 연결되어 있습니다.

예시

입력

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

출력

3