SPOJ Brasil

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 <= N <= 500) e M (1 <= M <= 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 != D; 0 <= S, D < N). Cada uma das M linhas seguintes contém três inteiros U, V e P (U != V; 0 <= U, V < N; 1 <= P <= 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 inteiros 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 requisistos ou um inteiro representando a extensão do quase menor caminho encontrado.

Exemplo de entrada
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

Saída para o exemplo de entrada
5
-1
6