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$ e $M$ , 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 distintos $S$ e $D$ , separados por um único espaço, indicando, respectivamente, os pontos distintos de partida e de destino. Cada uma das M linhas seguintes contém três inteiros $U$ , $V$ e $P$ , 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.