Encontrar o Caminho Mais Curto 2

Dispõe-se de um mapa constituído por n cidades e m estradas bidirecionais que ligam estas cidades. Cada estrada possui um comprimento inteiro não negativo, denotado por . A sua tarefa é determinar o comprimento do caminho mais curto entre a cidade 1 e a cidade n.

Entrada

A primeira linha contém dois inteiros separados por espaço, n e m (), que representam, respetivamente, o número de cidades e o número de estradas.

Nas próximas m linhas, cada linha contém três inteiros separados por espaço: , e , descrevendo uma estrada entre as cidades e com comprimento ().

Saída

Escreva um único inteiro que corresponda ao comprimento do caminho mais curto entre a cidade 1 e a cidade n.

Exemplos