Atalho (AB)
Problem
Você recebe uma descrição da rede rodoviária do país. Sua tarefa – encontre o comprimento do caminho mais curto entre as cidades A e B.
Entrada
A rede rodoviária é fornecida no arquivo de entrada da seguinte forma: a primeira linha contém os números N e K (1<=N<=100000, 0<=K<=300000), onde K – número de estradas. Cada uma das próximas K linhas contém uma descrição de uma via de mão dupla – três inteiros ai, bi e li (1aibiN, 1li106). Isso significa que existe uma estrada de comprimento li que leva da cidade ai à cidade bi. A última linha contém dois números A e B – número de cidades entre as quais é necessário calcular a distância mais curta (1<=A,B<=N )
Impressão
Você deve fornecer o número único – distância entre as cidades necessárias. Se for impossível ir da cidade A à cidade B por estrada, imprima –1.
Exemplos
| # |
Entrada |
Saída |
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |