Almost Shortest Path

Many cars come with a GPS navigation system that finds the shortest path between the start and the destination that the user enters. But if the traffic situation is ignored and everyone is guided along the shortest path, that path can become severely congested.

So you are building a navigation system, used only by yourself, that never guides along a shortest path and always guides along an almost shortest path instead.

An almost shortest path is the shortest path, from the start to the destination, that is made up only of roads which do not belong to any shortest path. In other words, remove every road that is used by one or more shortest paths, then find the shortest path using only the remaining roads.

There may be several almost shortest paths, and there may be none at all. When none exists, its length is defined as $-1$.

The input consists of several test cases.

The first line of each test case contains the number of places $N$ ($2 \le N \le 500$) and the number of roads $M$ ($1 \le M \le 10^4$). The places are numbered from $0$ to $N-1$.

The second line contains the start $S$ and the destination $D$. ($S \ne D$; $0 \le S, D < N$)

Each of the next $M$ lines contains three integers $U$, $V$, $P$, meaning there is a one-way road of length $P$ from $U$ to $V$. ($U \ne V$; $0 \le U, V < N$; $1 \le P \le 10^3$)

There is at most one road from $U$ to $V$, and the road $U \to V$ is different from the road $V \to U$.

The last line of the input contains two zeros, and this line must not be processed.

For each test case, print the length of the almost shortest path on its own line. If no almost shortest path exists, print $-1$.