K번째로 짧은 경로 찾기

여행자는 여러 도시를 지나 여행하려고 한다. 그는 항상 가장 짧은 경로만 고르는 대신, 너무 오래 걸리지 않으면서도 조금 다른 경로인 $k$번째 최단경로를 알고 싶어 한다.

도시 $1$에서 출발할 때, 각 도시까지 가는 $k$번째 최단경로의 소요 시간을 구하는 프로그램을 작성하라.

첫째 줄에 도시의 수 $n$, 도로의 수 $m$, 구하려는 순서 $k$가 주어진다. 조건은 $1 \le n \le 1000$, $0 \le m \le 250000$, $1 \le k \le 100$, $mk \le 3000000$이다.

다음 $m$개의 줄에는 도로 정보가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 $a$, $b$, $c$로 이루어지며, 이는 $a$번 도시에서 $b$번 도시로 가는 데 $c$의 시간이 걸린다는 뜻이다. 조건은 $1 \le a, b \le n$, $1 \le c \le 1000$이다.

도시 번호는 $1$번부터 $n$번까지이다. $1$번 도시는 시작 도시이며, 시작 도시와 도착 도시가 모두 같은 두 도로는 주어지지 않는다.

$n$개의 줄을 출력한다. $i$번째 줄에는 $1$번 도시에서 $i$번 도시로 가는 $k$번째 최단경로의 소요 시간을 출력한다.

경로의 소요 시간은 경로에 포함된 도로들의 이동 시간을 모두 더한 값이다. $i$번 도시에서 같은 $i$번 도시로 가는 최단경로는 $0$이지만, 일반적인 $k$번째 최단경로는 $0$이 아닐 수 있다. $k$번째 최단경로가 존재하지 않으면 $-1$을 출력한다.

경로는 같은 정점을 여러 번 지나도 된다.

추가 힌트는 제공되지 않는다.