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)$이 공백으로 구분되어 주어진다.

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