题目描述

$\red{BESSIE}$准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚. $\red{BESSIE}$也不想跑得太远,所以她想走最短的路经.

农场上一共有$\red{M (1 <= M <= 10,000)}$条路, 每条路连接两个用$\red{1..N(1 <= N <= 1000)}$标号的地点. 更方便的是,如果$\red{X>Y,}$则地点$\red{X}$的高度大于地 点$\red{Y}$的高度.

地点$\red{N}$是$\red{BESSIE}$的牛棚;地点$\red{1}$是池塘. 很快, $\red{BESSIE}$厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出$\red{K (1 <= K <= 100)}$条不同的路经.为了避免过度劳累,她想使这$\red{K}$条路经为最短的$\red{K}$条路经.

请帮助$\red{BESSIE}$找出这$\red{K}$条最短路经的长度.你的程序需要读入农场的地图, 一些从$\red{X_i}$到$\red{Y_i }$的路经和它们的长度$\red{(X_i, Y_i, D_i). }$

所有$\red{(X_i, Y_i, D_i)}$满足$\red{(1 <= Y_i < X_i}$; $\red{Y_i < X_i <= N, 1 <= D_i <= 1,000,000).}$

输入格式

第$\red{1}$行: $\red{3}$个数: $\red{N, M, }$和$\red{K}$

第 $\red{2..M+1}$行: 第 $\red{i+1 }$行包含$\red{3}$个数 $\red{X_i, Y_i, }$和 $\red{D_i, }$表示一条下坡的路.

输出格式

第$\red{1..K}$行: 第$\red{i}$行包含第$\red{i}$最短路经的长度,或$\red{-1}$

如果这样的路经不存在.如果多条路经有同样的长度,请注意将这些长度逐一列出.

样例

输入样例

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

提示

输出解释:

路经分别为

$\red{(5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),}$ $\red{(5-4-3-2-1).}$