题目描述

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

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

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

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

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

输入格式

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

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

输出格式

第${1..K}$行: 第${i}$行包含第${i}$最短路经的长度,或${-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

提示

输出解释:

路经分别为

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