??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.