31502번 - 만화에서 나오는 거 따라하고 그러면 안 된다

문제

토카는 어쩌다 마주친 아름다운 한별 선배에게 마음을 빼앗겨 버리고 말았다! 말을 걸고 싶었지만 그럴 자신이 없었던 토카는 한별 선배에게 말을 걸 만한 명분을 찾기 시작했다. 평소에 만화를 많이 읽던 토카는 그 명분을 만들 방법을 한 만화책에서 찾아냈다! 만화 속 남자 주인공과 여자 주인공이 등굣길에 벚꽃 아래에서 서로 부딪혔던 사건을 계기로 친해졌다는 내용을 보고 직접 따라 하기로 결심했다.

토카네 동네에는 벚나무가 없기 때문에 대신 은행나무가 있는 곳에서 시도하고자 한다. 토카네 동네는 1ドル$부터 $N$까지의 번호가 붙은 $N$개의 은행나무와 양 끝에 은행나무가 심어진 $M$개의 도로로 구성되어 있다. 모든 도로는 양방향 이동이 가능하며, 임의의 두 은행나무 사이를 항상 이동할 수 있다. 서로 다른 두 은행나무를 잇는 도로가 둘 이상일 수도 있다.

토카는 한별 선배 집 앞 은행나무의 번호와 등교하는 방법에 대해서 알아냈다. 한별 선배는 탁 트인 곳을 좋아해서 한 은행나무에서 인접한 다른 은행나무로 갈 때 연결된 도로가 가장 많은 은행나무로, 만약 그러한 은행나무가 여러 그루 있으면 가장 큰 번호를 가진 은행나무로 이동한다. 하지만 도로가 많은 길만 따라가다 보면 같은 도로만 빙빙 돌 수 있기 때문에 학교로 가는데 거치는 은행나무 수가 가장 적은 경로로 이동한다. 따라서 더 많은 도로가 연결된 은행나무라 하더라도 거치는 은행나무 수를 최소화할 수 없다면 그쪽으로는 향하지 않는다.

토카는 한별 선배와 같이 있는 시간을 길게 만들기 위해서 한별 선배가 등굣길에 지나치는 은행나무 중 토카네 집에서 가장 빨리 도착할 수 있는 은행나무에서, 만일 그런 은행나무가 여러 그루라면 번호가 가장 작은 은행나무 앞에서 부딪힌다는 계획을 세웠다. 김칫국을 마시고 있는 토카를 대신해 당신이 토카와 한별 선배가 부딪힐 운명의 은행나무를 알려 줘야 한다!

입력

첫 번째 줄에는 은행나무의 개수를 나타내는 $N (3 \le N \le 100,000円)$과 도로의 개수를 나타내는 $M(2 \le M \le 300,000円)$이 공백으로 구분되어 주어진다.

두 번째 줄에는 토카의 집과 인접한 은행나무 번호 $A$와 한별 선배의 집과 인접한 은행나무 번호 $B$와 학교와 인접한 은행나무 번호 $C$가 공백으로 구분되어 주어진다. $(1 \le A, B, C \le N;$ $A \neq B;$ $A \neq C;$ $B \neq C)$

마지막으로 세 번째 줄부터 $M$개의 줄에 걸쳐 도로 양 끝에 심겨 있는 은행나무 번호 $i, j$ $(1 \le i, j \le N;$ $i \neq j)$와 도로를 이동하는 데 걸리는 시간 $k$ $(1 \le k \le 10^9)$이 공백으로 구분되어 주어진다.

출력

토카가 가야 할 운명의 은행나무 번호를 출력한다.

제한

힌트