Frete

O senhor Satoshi passou anos reclamando da empresa de correios do seu país, porque ela sempre transportava suas encomendas usando um caminho que passava pelo número mínimo de cidades entre a cidade onde o senhor Satoshi mora e a cidade destino da encomenda. A empresa alegava que essa estratégia levava ao menor tempo para a entrega final da encomenda. O problema é que ele notou que essa estratégia da empresa nem sempre levava ao menor preço para o frete total. Se ele pudesse escolher o caminho por onde a encomenda deveria passar para ir da sua cidade para a cidade destino, ele poderia economizar bastante com o frete, já que não havia muita urgência para a maioria de suas encomendas.

Depois de muita reclamação, a empresa finalmente está dando aos clientes a opção de determinar o caminho por onde a encomenda deve passar. O senhor Satoshi, feliz da vida, agora quer a sua ajuda para implementar um programa que, dado o custo de transporte de uma encomenda entre vários pares de cidades pelo país, para os quais a empresa realiza entregas diretas, determine qual é o preço total mínimo para o frete entre a cidade onde ele mora e a cidade destino da encomenda.

Entrada

Saída

Restrições

• 2 ≤ N ≤ 100 e 1 ≤ M ≤ 1000
• 1 ≤ A,B ≤ N e A ≠ B
• 1 ≤ C ≤ 1000

Exemplos

5 6
1 2 4
1 3 3
4 3 6
4 5 2
2 4 1
3 5 5

7
	

7 10
1 2 5
3 1 32
1 4 3
2 3 4
2 6 20
6 3 1
6 4 9
6 5 6
3 7 18
5 7 2

18