当前没有测试数据。

题目描述

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

同时，贝西不想跑得太远，所以她只想沿着通向池塘的最短路径跑步。一共有 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​，描述一条下坡的道路。

输出格式

共 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**)**。

数据规模与约定

对于全部的测试点，保证 1≤N≤1,000，1≤M≤1×10^4，1≤K≤100，1≤Yi​<Xi​≤N，1≤Di​≤1×10^6，