[Usaco2008 Mar]牛跑步

贝茜准备通过从牛棚跑到池塘来锻炼身体。由于她只愿意沿下坡路奔跑，因此她会从牛棚跑到池塘，再步行返回牛棚。

农场中共有 $N$ 个地点，编号为 $1$ 到 $N$，以及 $M$ 条连接不同地点的道路。若 $X>Y$，则地点 $X$ 的海拔高于地点 $Y$。地点 $N$ 是贝茜的牛棚，地点 $1$ 是池塘。每条道路均从海拔较高的地点 $X_i$ 通向海拔较低的地点 $Y_i$，长度为 $D_i$。

贝茜不想总是沿同一条路径跑步，因此她希望找出从地点 $N$ 到地点 $1$ 的 $K$ 条不同路径。为了避免过度劳累，她需要这些路径是所有可行路径中最短的 $K$ 条。

请按长度从小到大的顺序，输出这 $K$ 条最短路径的长度。如果多条不同路径长度相同，则这些长度仍需分别输出。

输入格式

第一行包含三个整数 $N$、$M$ 和 $K$，分别表示地点数量、道路数量以及需要求出的最短路径数量。

接下来 $M$ 行，第 $i$ 行包含三个整数 $X_i$、$Y_i$ 和 $D_i$，表示一条从地点 $X_i$ 通向地点 $Y_i$、长度为 $D_i$ 的下坡道路。

输出格式

输出 $K$ 行。

第 $i$ 行输出第 $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\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$。

一共只有 $6$ 条可行路径，因此最后输出 $-1$。

数据范围

• $1\le N\le 10^3$，$1\le M\le 10^4$，$1\le K\le 100$；
• 对于每条道路，$1\le Y_i<X_i\le N$，$1\le D_i\le 10^6$。

来源与许可

本题为 USACO 2008 March 试题「牛跑步」，题面与测试数据整理自 BZOJ。

样例 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