Bad Cowtractors

베시(Bessie)는 농부 존(Farmer John)의 헛간 $N$개($2 \le N \le 1{,}000$) 사이에 값싼 인터넷 망을 구축하는 일을 맡았다. 헛간에는 $1$부터 $N$까지 번호가 매겨져 있다. 농부 존은 이미 사전 조사를 마쳐, 헛간 쌍을 잇는 연결 경로 후보 $M$개($1 \le M \le 20{,}000$)를 찾아 두었다. 각 연결 경로에는 비용 $C$($1 \le C \le 100{,}000$)가 붙어 있다. 농부 존은 망을 연결하는 데 드는 비용을 최소로 쓰고 싶어 하며, 심지어 베시에게 품삯조차 주지 않으려 한다.

농부 존이 품삯을 주지 않으리라는 것을 안 베시는 일부러 최악으로 일하기로 결심한다. 베시는 설치할 연결들의 집합을 다음 조건을 모두 만족하도록 골라야 한다.

1. 선택한 연결들의 총 비용이 가능한 한 커야 한다.
2. 모든 헛간이 서로 연결되어 있어야 한다(설치된 연결들의 경로를 따라 어떤 헛간에서든 다른 어떤 헛간으로도 갈 수 있어야 한다).
3. 연결들 사이에 사이클이 없어야 한다(사이클이 있으면 농부 존이 쉽게 알아챌 것이다).

조건 2와 3에 의해, 최종 연결 집합은 하나의 트리(tree)를 이루게 된다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• $2$번째 줄부터 $M+1$번째 줄까지: 각 줄에는 공백으로 구분된 세 정수 $A$, $B$, $C$가 주어지며, 이는 헛간 $A$와 $B$를 잇는 비용 $C$의 연결 경로를 뜻한다.

• 첫째 줄: 모든 헛간을 연결하는 신장 트리 중 총 비용이 가장 큰 값을 정수 하나로 출력한다. 모든 헛간을 연결하는 것이 불가능하면 $-1$을 출력한다.