K Shortest Downhill Paths

Bessie has finally experienced the consequences of laziness and decided to improve fitness by jogging downhill from the barn (the highest point) to the pond (the lowest point) several times each week. She prefers not to run too hard and therefore only runs along the shortest downhill route from the cow shed starting at the highest-numbered farm (N) to the pond at farm 1. However, after a week she got bored of the monotony and now wants to try K different routes. In other words, she wants the K shortest routes from farm N to farm 1 among all downhill paths. Two routes are considered different if the sequences of roads (edges) they use are different.

You are given a list of M roads. Each road is represented by a triplet \((X_i, Y_i, D_i)\), meaning there is a downhill road from farm \(X_i\) to farm \(Y_i\) with length \(D_i\). It is guaranteed that if \(X_i > Y_i\) then farm \(X_i\) is at a higher elevation than farm \(Y_i\), ensuring that all roads lead downhill. Your task is to compute the lengths of the K shortest paths from farm \(N\) (the cow shed) to farm \(1\) (the pond). If less than K paths exist, output \(-1\) for each missing path.

Note: All formulas are rendered in LaTeX format. For example, the road information is given by \((X_i, Y_i, D_i)\) and the two endpoints are: source \(N\) and destination \(1\).

inputFormat

The input begins with a single line containing three integers \(N\), \(M\), and \(K\) where:

• \(N\) is the number of farms, numbered from 1 to \(N\) (with \(N\) being the cow shed and 1 being the pond).
• \(M\) is the number of downhill roads.
• \(K\) is the number of shortest paths to find.

Each of the next \(M\) lines contains three integers \(X_i\), \(Y_i\), and \(D_i\) representing a road from farm \(X_i\) to farm \(Y_i\) with length \(D_i\). It is guaranteed that \(X_i > Y_i\) for each road.

outputFormat

Output exactly \(K\) lines where the \(i\)th line contains the length of the \(i\)th shortest path from farm \(N\) to farm \(1\). If there are fewer than \(K\) valid paths, output \(-1\) for each missing path.

sample

4 5 3
4 3 2
4 2 3
3 2 1
3 1 5
2 1 2

5
5
7