时间限制：1秒　　内存限制：256M

---

【题目描述】

　　贝西准备用从牛棚跑到池塘的方法来锻炼，但是因为太懒，她准备沿着下坡的路跑到池塘，然后回到牛棚。

　　贝西也不想跑得太远，所以她想走最短的路径。农场上一共有 \(m\) 条道路，每条路连接两个地点（编号是 \(1 \sim n\) 范围内的整数），更方便的是，对于编号 \(x\) 和编号 \(y\) 的点，如果 \(x>y\)，则地点 \(x\) 的高度大于地点 \(y\) 的高度，地点 \(n\) 是贝西的牛棚，地点 1 是池塘。

　　很快，贝西厌倦了一直走同一条路，所以她想走不同的路，更明确地讲，她想找出 \(k\) 条不同的路径，为了避免过度劳累，她想使这 \(k\) 条路径为最短的 \(k\) 条路径。

　　请帮助贝西找出这 \(k\) 条最短路径长度，你的程序需要读入农场的地图，一些从 \(x\) 到 \(y\) 的路和他们的长度 \((x,y,d)\)，所有 \((x,y,d)\) 都满足 \(1 ≤ y < x ≤ n, 1≤ d ≤ 1000000\)。

【输入格式】

　　第 1 行：包含 3 个整数 \(n,m,k\)。
　　第 2 到第 \(m+1\) 行：第 \(i+1\) 行包含 3 个数：\(x,y,d\)，表示一条下坡的路。

【输出格式】

　　第 1 到 \(k\) 行，第 \(i\) 行包含第 \(i\) 短路径的长度。如果不存在这样的路径，则输出 -1。如果有多条路径有同样的长度，请注意将谢谢长度注意列出。

【输入输出样例】

　Input

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

　Output

1
2
2
3
6
7
-1

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤1000\)，\(1≤m≤10000\)，\(1≤k≤100\)。

【来源】

　　Mr.he