Segundo Caminho Mais Curto
Você tem
n cidades e m estradas bidirecionais que as conectam. Cada estrada tem um comprimento correspondente . Emil, um viajante aventureiro, quer ir da cidade 1 até a cidade n usando essas estradas. No entanto, ele tem um plano diferente do habitual: vai escolher o menor caminho entre todos que sejam estritamente maiores do que o caminho mais curto possível.Em outras palavras, sua tarefa é ajudar Emil a determinar o comprimento do segundo caminho mais curto da cidade
1 até a cidade n.Entrada
A primeira linha da entrada contém dois inteiros
n e m, que indicam o número de cidades e o número de estradas, respectivamente.Saída
Imprima um único inteiro que represente o comprimento do segundo caminho mais curto da cidade
1 até a cidade n.Exemplos
Entrada | Saída |
6 7
1 2 3
2 3 4
3 6 5
2 6 9
1 4 3
4 5 8
5 6 2
| 13 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB