Quase menor caminho

Achar um caminho que vai de um ponto inicial até um ponto de destino dados um conjunto de pontos e a extensão das rotas que os conectam é um problema já bem conhecido, e já até é parte de nosso dia-a-dia, uma vez que programas de caminho mínimo estão largamente distribuídos hoje em dia.

A maioria das pessoas normalmente gosta bastante dessas aplicações já que elas tornam suas vidas mais fáceis. Bem, talvez nem tão mais fáceis.

Agora que quase todo mundo tem acesso a aparelhos de GPS capazes de calcular os caminhos mais curtos a maioria das rotas que formam o caminho mais curto estão ficando lentas devido ao tráfego pesado. Como a maioria das pessoas tenta seguir o mesmo caminho, não vale mais a pena seguir essas direções.

Com isso em mente, seu chefe pediu a você que desenvolvesse uma nova aplicação à qual somente ele vai ter acesso, poupando tempo sempre que ele tiver uma reunião ou qualquer evento urgente. Ele pede a você que o programa não deve dizer o menor caminho, mas o quase menor caminho. Ele define o quase menor caminho como o menor caminho que vai de um ponto inicial até um um ponto de destino de forma que nenhuma rota entre dois pontos consecutivos pertence a qualquer caminho mínimo entre o ponto de partida e o de destino.

Por exemplo, suponha que a figura abaixo representa o mapa dado, com círculos representando localizações e linhas representando rotas diretas, de mão única com as distâncias indicadas. O ponto de partida está marcado como S e o de destino está marcado como D. As linhas em negrito pertencem a um caminho mínimo (nesse caso existem dois caminhos mínimos, cada um com extensão 4). Logo, o quase menor caminho seria o indicado com linhas pontilhadas (extensão 5), já que nenhuma rota entre dois pontos consecutivos pertence a nenhum caminho mínimo. Note que poderia existir mais de uma resposta possível, por exemplo, se a rota com extensão 3 tivesse extensão 1. Bem como poderia inexistir uma resposta certa.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém dois inteiros $N\ (2 \leq N \leq 500)$ e $M\ (1 \leq M \leq 10^4)$ , separados por um espaço, indicando, respectivamente, o número de pontos no mapa e o número de rotas de mão única conectando dois pontos diretamente. Cada ponto é identificado por um único inteiro entre $0$ e $N - 1$ . A segunda linha contém dois inteiros $S$ e $D$ , separados por um único espaço, indicando, respectivamente, os pontos de partida e de destino $(S \neq D, 0 \leq S, D < N)$ . Cada uma das M linhas seguintes contém três inteiros $U, V$ e $P\ (U \neq V, 0 \leq U, V < N, 1 \leq P \leq 10^3)$ , separados por espaço, indicando a existência de uma rota de $U$ para $V$ com distância $P$ . Existe no máximo uma rota de um ponto $U$ até um ponto $V$ , mas perceba que a existência de uma rota de $U$ para $V$ não implica a existência de uma rota de $V$ para $U$ e, se tal estrada existir, ela pode ter extensão diferente. O fim da entrada é indicado por uma linha contendo apenas dois zeros separados por um espaço.

Saída

Para cada caso de teste na entrada, seu programa deve imprimir uma única linha, contendo -1 se não for possível cumprir os requisitos ou um inteiro representando a extensão do quase menor caminho encontrado.

Exemplos

Entrada

Saída

7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0

-1