题目描述

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

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

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

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

输入格式

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

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

输出格式

共 $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 

提示

样例 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)$。

数据规模与约定

对于全部的测试点，保证 $1 \le N \le 1,000$，$1 \le M \le 1\times10^4$，$1 \le K \le 100$，$1 \le Y_i < X_i\le N$，$1 \le D_i \le 1\times 10^6$，