Cow Jogging

Bessie has taken heed of the evils of sloth and decided to get fit by jogging from the barn to the pond several times a week. To avoid working too hard, she only jogs downhill to the pond and then ambles back to the barn at her leisure.

The pastures are numbered $1$ through $N$ ($1 \le N \le 1{,}000$). Whenever $X > Y$, the cow path from pasture $X$ to pasture $Y$ runs downhill. Pasture $N$ is the barn at the top of the hill, and pasture $1$ is the pond at the bottom.

Tired of always taking the same route, Bessie wants variety: she would like to know the lengths of the $K$ shortest routes from the barn to the pond ($1 \le K \le 100$). Two routes are considered different if they consist of a different sequence of cow paths.

You are given $M$ downhill cow paths ($1 \le M \le 10{,}000$). Cow path $i$ goes from pasture $X_i$ to pasture $Y_i$ ($1 \le Y_i < X_i \le N$) and has length $D_i$ ($1 \le D_i \le 1{,}000{,}000$).

• Line 1: three space-separated integers $N$, $M$, and $K$.
• Lines 2 through $M+1$: each line describes one downhill cow path with three space-separated integers $X_i$, $Y_i$, and $D_i$.

• Print $K$ lines. Line $i$ contains the length of the $i$-th shortest route, or $-1$ if no such route exists. If a shortest-route length occurs multiple times, print it that many times.

For the graph with $N = 5$, the routes from the barn (pasture $5$) to the pond (pasture $1$) are $5 \to 1$, $5 \to 3 \to 1$, $5 \to 2 \to 1$, $5 \to 3 \to 2 \to 1$, $5 \to 4 \to 3 \to 1$, and $5 \to 4 \to 3 \to 2 \to 1$, with lengths $1, 2, 2, 3, 6, 7$ respectively.