대회 당일

Matt, Nick, Tim은 한집에 살면서 함께 프로그래밍 대회에 나간다. 큰 대회가 다가오는데, 최근 C#을 배운 Matt는 실력을 뽐내려고 Nick과 Tim을 상대로 혼자 겨루기로 했다. Nick과 Tim은 둘의 Fortran 95 실력을 합치면 Matt를 이긴다고 자신한다.

Nick은 대회 당일에 Matt의 심리를 흔들려고 Matt와 다른 길로 대회장에 가자고 제안한다. 자기들이 다른 길로 간다는 것을 Matt가 보도록 세 사람은 같은 시각에 집을 나선다. 하지만 Matt는 한발 앞서서 집에서 대회장까지 가장 빠른 경로를 이미 계산해 두었다.

Tim은 같은 풍경에 기름을 낭비하기 싫어해서, 두 사람의 경로는 같은 교차로를 두 번 지나지 않는다. 도로망에는 교차로 $N$개와 일방통행 도로 $M$개가 있다. 각 도로를 지나는 데 걸리는 시간 $T$(분)는 이미 알려져 있다. 집과 대회장은 서로 다른 교차로에 있다.

경로는 집에서 출발해 대회장에서 끝나고, 매 단계마다 도로 하나를 따라가며, 같은 교차로를 두 번 지나지 않는 교차로의 나열이다. Matt는 가장 빠른 경로로 간다. Nick과 Tim은 Matt의 경로를 뺀 나머지 경로 중 가장 빠른 경로로 간다. 서로 다른 두 경로가 모두 최소 시간이면 Nick과 Tim은 다른 하나를 골라 Matt와 같은 시각에 도착하므로 답은 $0$이다.

Nick과 Tim은 Matt보다 몇 분 늦게 도착할까?

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에 정수 네 개 $N$, $M$, $F$, $C$가 주어진다. ($2 \le N \le 8000$, $1 \le M \le 8000$, $1 \le F, C \le N$, $F \ne C$) $N$은 교차로의 수, $M$은 도로의 수, $F$는 집이 있는 교차로 번호, $C$는 대회장이 있는 교차로 번호이다.

다음 $M$개의 줄에 정수 세 개 $i$, $j$, $T$가 주어진다. ($1 \le i, j \le N$, $0 < T \le 2 \times 10^5$) 교차로 $i$에서 교차로 $j$로 가는 일방통행 도로가 있고 지나는 데 $T$분이 걸린다는 뜻이다.

자기 자신으로 이어지는 도로는 없고, 같은 교차로 쌍을 같은 방향으로 잇는 도로가 두 개 이상 있지도 않다. $F$에서 $C$로 가는 경로는 항상 하나 이상 있다.

입력의 마지막 줄은 0 0 0 0이며 테스트 케이스가 아니다.

각 테스트 케이스마다 한 줄씩 출력한다. Nick과 Tim이 Matt보다 몇 분 늦게 도착하는지 출력한다. Matt의 경로가 집에서 대회장으로 가는 유일한 경로라면 대신 Matt wins.를 출력한다.