Finding the K-th Shortest Path

A traveler plans to move through several cities. Instead of always choosing only the shortest route, he wants a slightly different route that is still not too slow: the $k$-th shortest path.

Starting from city $1$, write a program that finds the travel time of the $k$-th shortest path to every city.

The first line contains the number of cities $n$, the number of roads $m$, and the rank $k$ to find. The constraints are $1 \le n \le 1000$, $0 \le m \le 250000$, $1 \le k \le 100$, and $mk \le 3000000$.

Each of the next $m$ lines contains one road. A road is given by three integers $a$, $b$, and $c$, meaning that traveling from city $a$ to city $b$ takes time $c$. The constraints are $1 \le a, b \le n$ and $1 \le c \le 1000$.

Cities are numbered from $1$ to $n$. City $1$ is the starting city. No two roads have both the same starting city and the same ending city.

Print $n$ lines. On the $i$-th line, print the travel time of the $k$-th shortest path from city $1$ to city $i$.

The travel time of a path is the sum of the times of all roads on that path. The shortest path from city $i$ to the same city $i$ has length $0$, but a general $k$-th shortest path may not have length $0$. If the $k$-th shortest path does not exist, print $-1$.

A path may visit the same vertex more than once.

No additional hint is provided.