SPOJ Brasil

Cansado dos constantes engarrafamentos que enfrenta todo dia para chegar ao trabalho com seu carro, Antônio resolveu reclamar com a secretaria responsável pelo controle de tráfego de sua cidade. Porém, ao entrar em contato com tal órgão, descobriu que este disponibiliza mapas das ruas da cidade, com o tempo que um carro costuma gastar para atravessar cada uma das ruas durante o período de engarrafamento. Com estas informações, ele pôde descobrir o caminho mais rápido de sua casa até seu local de trabalho, podendo, assim, acordar mais tarde e dormir um pouco mais todo dia.

Empreendedor nato, Antônio percebeu que as informações colhidas junto à secretaria poderiam ser úteis para ele de outra forma. Decidiu, então, criar um programa de computador para ajudar seus colegas de trabalho que enfrentam o mesmo problema, indicando os caminhos mais rápidos entre pontos da cidade selecionados pelo usuário. Naturalmente, esta ajuda não será gratuita, já que Antônio pretende cobrar pelo uso do programa.

Antônio, porém, não tem tempo livre suficiente para programar. Como você é um estagiário da empresa que está logo abaixo de Antônio, ele pede que você escreva um programa que, dado um mapa com as ruas e o tempo necessário para atravessar cada uma, calcule o tempo mínimo para se ir de um determinado local de origem a um determinado local de destino.

Entrada

A entrada é composta de vários casos de teste. Cada caso de teste é iniciado com uma linha contendo dois números inteiros, n e m (1 <= n <= 100, 0 <= m <= 10000), representando, respectivamente, o número de locais da cidade (identificados por inteiros de 1 a n) e o número de ruas a serem considerados.

A seguir, há m linhas, cada uma contendo três inteiros, i, j e t (1 <= i, j <= n, i ≠ j, 1 <= t <= 1000), indicando que há uma rua de mão única ligando os locais i e j, nesta ordem, e cujo tempo de travessia é t. Para cada par de locais i e j, haverá no máximo uma rua ligando i a j e no máximo uma rua ligando j a i.

Finalmente, a última linha do caso de teste contém dois inteiros, s e d (1 <= s, d <= n), respectivamente, os locais inicial e final para os quais devemos calcular o tempo mínimo de trajeto.

A entrada termina quando n = m = 0.

Saída

Para cada caso de teste, seu programa deve imprimir uma linha com um único inteiro, representando o tempo mínimo necessário para se deslocar do local s ao local d. Se não for possível alcançar o local d a partir do local s, imprima -1 como resposta.

Exemplo

Entrada:
3 3
1 2 2
1 3 7
2 3 3
1 3
3 3
1 2 3
1 3 7
2 3 5
1 3
3 2
1 2 2
2 1 3
1 3
4 6
1 2 5
1 3 3
2 4 3
3 2 2
4 1 4
4 3 9
2 3
0 0

Saída:
5
7
-1
10