??Terceiro Desafio: O Caminho do Chocolate??

Como dito no problema iniciante, o coelhinho da Páscoa passou uma série de desafios para Lumy resolver até ela conseguir chegar no grande prêmio: o melhor ovo de Páscoa do mundo. Depois de passar pelo primeiro e segundo desafios, Lumy terá agora que resolver o desafio final!

Agora finalmente Lumy poderá ir até o seu grande prêmio, mas ela terá que fazer isso de uma maneira um pouco diferente.

Dado $$N$$ pontos de interesse na cidade e $$M$$ rotas uni-direcionadas, em que a $$i-esima$$ rota liga do ponto $$A_i$$ para o $$B_i$$ e demora um tempo $$C_i$$ para ser a travessada. O ponto de interesse $$1$$ é a casa de Lumy e o ponto de interesse $$N$$ é onde o melhor ovo de Páscoa do mundo está localizado.

O problema é que Lumy não pode ir até seu prêmio pelo menor caminho, ela tem que percorrer o $$k-esimo$$ menor caminho da casa dela até o ovo de chocolate. O coelhinho disse que se ela não seguir um caminho que tenha o mesmo valor que o $$k-esimo$$ menor caminho, ele pegará o ovo e ela não ganhará nada. Mas além de passar pela $$k-esimo$$ menor caminho, ela tem que dizer o valor dos $$k$$ menores caminhos de $$1$$ até $$N$$.

Formalmente, dado um grafo com $$N$$ vértices e $$M$$ arestas direcionadas e com peso, retorne os valores dos $$k$$ menores caminhos de $$1$$ até $$N$$. Lembrando que uma mesma cidade pode ser visitada mais de uma vez, dois caminho são considerados diferentes se o $$i-esimo$$ vértice passado pelo primeiro caminho é diferente do segundo para algum $$i$$, e caminhos diferentes com o mesmo tempo devem ser contabilizados diferentemente. (leia o enunciado original no final da página para mais detalhes).

Entrada:

A primeira linha tem 3 inteiros $$N,M,K$$, que representam a quantidade de pontos de interesse, a quantidade de arestas e quantas menores rotas você tem que retornar.

As próximas $$M$$ linhas contém 3 inteiros cada, $$A_i,B_i,C_i$$, que representam o ponto inicial, final e o tempo da $$i-esima$$ rota.

Saída:

Imprima $$K$$ inteiros: a duração dos $$K$$ menores caminhos de $$1$$ até $$N$$, em ordem crescente.

Limites:

• $$1\leq N\leq 10^5$$
• $$1\leq M\leq 2*10^5$$
• $$1\leq A_i,B_i\leq N$$
• $$1\leq C_i\leq 10^9$$
• $$1 \leq K \leq 10$$

Exemplo:

4 4 7

Explicação: As menores rotas são $$1 \rightarrow 3 \rightarrow 4$$ (preço $$4), $$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$$ (preço $$4$$) e $$1\rightarrow 2 \rightarrow 4$$ (preço $$7$$).

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