Description

Bessie has finally tasted the consequences of laziness and decides to jog from the barn to the pond several times a week to get in shape. Of course, she does not want to overexert herself, so she only plans to jog downhill from the barn to the pond, then leisurely walk back to the barn.

At the same time, Bessie does not want to run too far, so she wants to run along the shortest route to the pond. There are $M$ roads in total, each connecting two pastures. The pastures are numbered from $1$ to $N$. If $X > Y$, it means pasture $X$ is higher than pasture $Y$, i.e., downhill roads go from $X$ to $Y$. Pasture $N$ is the barn (the highest point), and pasture $1$ is the pond (the lowest point).

However, after a week, Bessie gets bored of the monotony and wants to try different routes. For example, she hopes there can be $K$ different routes. To avoid getting too tired, she wants these $K$ routes to be the $K$ shortest routes from the barn to the pond. Two routes are considered different if the sequences of roads they contain are different.

Please help Bessie compute her training intensity by finding the lengths of the $K$ shortest paths in the pasture network. You are given a list of roads between pastures, where each road is represented by $(X_i, Y_i, D_i)$, meaning there is a downhill road from $X_i$ to $Y_i$ of length $D_i$.

Input Format

The first line contains three space-separated integers $N, M, K$.

Each of the next $M$ lines contains three space-separated integers $X_i, Y_i, D_i$, describing a downhill road.

Output Format

Output $K$ lines. On the $i$-th line, output the length of the $i$-th shortest route. If fewer than $K$ routes exist, output $-1$ for the remaining lines. If multiple distinct routes have the same length, they should all be counted; equal lengths may appear multiple times.

5 8 7 
5 4 1 
5 3 1 
5 2 1 
5 1 1 
4 3 4 
3 1 1 
3 2 1 
2 1 1 

1 
2 
2 
3 
6 
7 
-1 

Hint

Sample 1 Explanation: These routes 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)$.

Constraints: For all test points, it is guaranteed that $1 \le N \le 1,000$, $1 \le M \le 1 \times 10^4$, $1 \le K \le 100$, $1 \le Y_i < X_i \le N$, $1 \le D_i \le 1 \times 10^6$.

Translated by ChatGPT 5