거의 최단 경로

많은 자동차의 GPS 내비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 찾아 준다. 하지만 교통 상황을 고려하지 않고 모두를 최단 경로로만 안내하면, 그 경로에 차가 몰려 극심한 정체가 생길 수 있다.

그래서 오직 자기 자신만 사용하는, 절대로 최단 경로를 안내하지 않고 항상 "거의 최단 경로"만 안내하는 내비게이션을 만들려고 한다.

거의 최단 경로란, 출발점에서 도착점까지 가는 경로 중에서 어떤 최단 경로에도 포함되지 않는 도로만으로 이루어진 경로 가운데 가장 짧은 것을 말한다. 다시 말해, 하나 이상의 최단 경로에 사용되는 도로를 모두 제거한 뒤, 남은 도로만으로 이동했을 때의 최단 경로이다.

거의 최단 경로는 여러 개 존재할 수도 있고, 아예 존재하지 않을 수도 있다. 존재하지 않는 경우 그 길이는 $-1$로 정의한다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 장소의 수 $N$ ($2 \le N \le 500$)과 도로의 수 $M$ ($1 \le M \le 10^4$)이 주어진다. 장소에는 $0$번부터 $N-1$번까지 번호가 매겨져 있다.

둘째 줄에는 출발점 $S$와 도착점 $D$가 주어진다. ($S \ne D$; $0 \le S, D < N$)

다음 $M$개 줄에는 도로의 정보가 세 정수 $U$, $V$, $P$로 주어지며, 이는 $U$에서 $V$로 가는 길이 $P$의 단방향 도로가 있다는 뜻이다. ($U \ne V$; $0 \le U, V < N$; $1 \le P \le 10^3$)

$U$에서 $V$로 가는 도로는 최대 한 개이며, $U \to V$ 도로와 $V \to U$ 도로는 서로 다른 도로이다.

입력의 마지막 줄에는 $0$이 두 개 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 거의 최단 경로의 길이를 한 줄에 출력한다. 거의 최단 경로가 존재하지 않으면 $-1$을 출력한다.