Desconto Único

Alex mora na cidade 1 e deseja chegar à cidade n. Ele quer encontrar a rota de voo mais económica, tendo em conta que dispõe de um cupão de desconto. Esse cupão de desconto pode ser usado apenas uma vez, para reduzir para metade o preço de um único voo ao longo do percurso. Quando ele utiliza o cupão num voo cujo preço é x, o custo passa a ser .
Encontre o preço da rota mais barata da cidade 1 até à cidade n.

Entrada

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

As próximas m linhas descrevem os voos. Em cada linha, encontram-se três inteiros, a, b e , separados por espaço (), indicando um voo bidirecional da cidade a para a cidade b, com um preço de .

Saída

Imprime um único inteiro, que representa o preço da rota mais barata entre a cidade 1 e a cidade n.

Exemplos