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