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.