Desconto de Viagens

Dado um grafo com $N$ vértices e $M$ arestas direcionadas com peso, você precisa dizer qual o valor da menor rota para ir de $1$ até $N$. Mas você tem um cupom de desconto que pode ser usado exatamente uma vez: ao usá-lo em uma viagem, você diminui seu preço pela metade (arredondando para baixo).

Entrada:

A primeira contém dois inteiros $N$ e $M$, que são respectivamente a quantidade de vértices e arestas.

As próximas $M$ linhas possuem três inteiros $a$, $b$, $c$, que significa que existe uma aresta direcionada saindo do vértice $a$, indo para o vértice $b$, com peso $c$.

Sempre é possível ir do vértice $1$ para o vértice $N$.

Saída:

Imprima um inteiro: o preço da menor rota de $1$ para $N$, sabendo que você pode usar um cupom de desconto em exatamente uma aresta, fazendo com que o peso dela se torne $\lfloor c/2 \rfloor$ (se seu peso original era $c$).

Limites:

• $1\leq N \leq 10^5$
• $1\leq M \leq 2*10^5$
• $1\leq a,b \leq N$
• $1\leq c \leq 10^9$

Exemplo:

3 4
1 2 3
2 3 1
1 3 7
2 1 5

2

Para submeter sua solução, use esse link.