Mania de Par
Pat quer viajar para uma outra cidade, mas quer que a quantidade de pedágios pagos seja par. Sabendo que cada estrada é bidirecional e possui um pedágio com um custo $$G$$, ajude Pat a descobrir qual é o menor custo que ela terá que pagar para chegar em seu destino obedecendo a condição.
Entrada:
A entrada consiste de diversas linhas.
A primeira linha possui dois inteiros $$C$$ e $$V$$, o número de cidades e a quantidade de estradas, respectivamente. Cada uma das $$V$$ linhas apresenta 3 inteiros: $$C_1, C_2, G$$, indicando que o pedágio entre as cidades $$C_1$$ e $$C_2$$ tem custo $$G$$.
Pat está na cidade $$1$$ e quer chegar na cidade $$C$$.
Saída:
O seu programa deve imprimir uma única linha contendo o menor custo para que Pat chegue à cidade $$C$$ pagando um número par de pedágios. Caso isso não seja possível, imprima -1.
Limites:
- $$2\leq C\leq 10^4$$
- $$0\leq V\leq 50000$$
- $$1\leq C_1, C_2\leq C$$
- $$1\leq G\leq 10^4$$
Exemplo:
| Entrada | Saída |
| 4 4 1 2 2 2 3 1 2 4 10 3 4 6 |
12 |
| Entrada | Saída |
| 5 6 1 2 3 2 3 5 3 5 2 5 1 8 2 4 1 4 5 4 |
-1 |
Para submeter a sua solução, use esse link