#1968 테러리스트 Joo

15  1 s   128 MB  

Description

왕국 제일테러범 Joo는 오늘도 테러계획을 세운다. 마침 그에게 들어온 소식은 왕국의 섬 연결 계획도.

왕국의 고위간부과의 하룻밤을 통해 그는 왕국에서 모든 섬이 연결되면서 최소비용을 투자하게끔 다리를 지으려고 한다는 것을 알아내었다.

Joo는 돈은 없지만 남자는 스케일이 커야한다면서 한 섬을 폭파하여 최대한 많은 섬 그룹들이 연결되지 않도록 하려고 한다.

왕국수사기관 ANSI를 도와 Joo가 어떤 다리를 파괴하려고 하는지 알아내자.

Input

먼저 첫줄에는 섬의 갯수 N(1<=N<=1,000)과 예정단계의 다리의 갯수 M(1<=M<=10,000)이 들어온다.

이때 편의상 섬의 고유번호를 1부터 N까지 매기기로 하자.

두번째 줄 부터 M+1줄 까지는 A B V (A번섬과 B번섬을 연결할경우 V만큼의 돈이 소모된다는 뜻이다)가 입력된다.

이때 입력되는 A와 B를 이을 때 지어질 다리는 유일하다.

Output

Joo가 폭파하려는 섬의 고유번호를 출력한다.

답이 여러개 존재할 경우, 모두 출력한다.

Sample Input

Sample Output

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

HINT

예제에서 2번섬, 3번섬, 4번섬을 폭파할경우 연결되지 않는 섬의 그룹은 2그룹이 된다.