1378: Cow Jogging G

贝西终于尝到了懒惰的后果，决定每周从谷仓到池塘慢跑几次来健身。当然，她不想跑得太累，所以她只打算从谷仓慢跑下山到池塘，然后悠闲地散步回谷仓。

同时，贝西不想跑得太远，所以她只想沿着通向池塘的最短路径跑步。一共有 $M$ 条道路，其中每一条都连接了两个牧场。这些牧场从 $1$ 到 $N$ 编号，如果 $X>Y$，则说明牧场 $X$ 的地势高于牧场 $Y$，即下坡的道路是从 $X$ 通向 $Y$ 的，$N$ 为贝西所在的牛棚（最高点），1 为池塘（最低点）。

然而，一周之后，贝西开始对单调的路线感到厌烦，她希望可以跑不同的路线。比如说，她希望能有 $K$ 种不同的路线。同时，为了避免跑得太累，她希望这 $K$ 条路线是从牛棚到池塘的路线中最短的 $K$ 条。如果两条路线包含的道路组成的序列不同，则这两条路线被认为是不同的。

请帮助贝西算算她的训练强度，即将牧场网络里最短的 $K$ 条路径的长度分别算出来。你将会被提供一份牧场间路线的列表，每条道路用 $(Xi,Yi,Di)$ 表示，意为从 $Xi$到 $Yi$ 有一条长度为 $Di$ 的下坡道路。

第一行三个用空格分开的整数 $N,M,K$，其中 。

第二行到第 $M+1$ 行每行有三个用空格分开的整数 $Xi,Yi,Di$，描述一条下坡的道路。

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

样例 1 解释

这些路线分别为 (5-1)、(5-3-1)、(5-2-1)、(5-3-2-1)、(5-4-3-1) 和 (5-4-3-2-1)。

数据规模与约定

对于全部的测试点，保证$1\le N\le 1,000$，$1\le M\le 1\times 10^4$，$1\le K\le 100$，$1\le Yi<Xi\le N$，$1\le Di\le 1\times 10^6$，