// problem #85

도시 분할 계획

N개의 집을 두 개의 마을로 나눈다. 각 마을은 연결되어야 하고, 유지비(선택한 길의 비용 합)를 최소화한다. 즉 최소 스패닝 트리에서 가장 큰 간선을 제거한 값을 구하시오.

입력

첫 줄 집 수 N, 길 수 M. 이후 M개 줄에 a b c.

출력

남는 길 유지비의 최솟값.

제한

• 2 ≤ N ≤ 100,000
• 1 ≤ M ≤ 1,000,000
• 1 ≤ c ≤ 1,000

예제

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

8