소의 조깅

Bessie는 게으름의 해악을 깨닫고, 건강을 위해 일주일에 여러 번 헛간에서 연못까지 조깅하기로 했다. 너무 힘들지 않도록 연못까지는 내리막으로만 뛰어 내려가고, 헛간으로는 천천히 걸어서 돌아온다.

목초지는 $1$번부터 $N$번까지 번호가 매겨져 있다 ($1 \le N \le 1{,}000$). $X > Y$이면 목초지 $X$에서 목초지 $Y$로 가는 소 길은 내리막이다. 목초지 $N$은 언덕 꼭대기의 헛간이고, 목초지 $1$은 언덕 아래의 연못이다.

Bessie는 매번 같은 길로만 가는 것이 지겨워 다양한 길로 뛰고 싶어한다. 구체적으로, 헛간에서 연못까지 가는 경로 중 가장 짧은 $K$개의 경로 길이를 알고 싶다 ($1 \le K \le 100$). 두 경로는 지나는 소 길의 나열이 다르면 서로 다른 경로로 본다.

$M$개의 내리막 소 길이 주어진다 ($1 \le M \le 10{,}000$). 소 길 $i$는 목초지 $X_i$에서 $Y_i$로 이어지며 ($1 \le Y_i < X_i \le N$), 길이는 $D_i$이다 ($1 \le D_i \le 1{,}000{,}000$).

• 첫째 줄: 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다.
• 둘째 줄부터 $M+1$째 줄까지: 각 줄에 내리막 소 길을 나타내는 세 정수 $X_i$, $Y_i$, $D_i$가 공백으로 구분되어 주어진다.

• $K$개의 줄을 출력한다. $i$째 줄에는 $i$번째로 짧은 경로의 길이를 출력하고, 그런 경로가 없으면 $-1$을 출력한다. 같은 길이의 최단 경로가 여러 개 있으면 그 개수만큼 반복해서 출력한다.

$N = 5$인 그래프에서 헛간(목초지 $5$)에서 연못(목초지 $1$)까지의 경로는 $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$, $5 \to 4 \to 3 \to 2 \to 1$의 여섯 가지이며, 길이는 각각 $1, 2, 2, 3, 6, 7$이다.