题目描述

Bessie 准备用从牛棚跑到池塘的方法来锻炼。但是因为她懒，她只准备沿着下坡的路跑到池塘，然后走回牛棚。Bessie 也不想跑得太远，所以她想走最短的路径。农场上一共有 $m$ 条路, 每条路连接两个地点，共有 $n$ 个地点。更方便的是，如果 $x>y$，则地点 $x$ 的高度大于地点 $y$ 的高度。地点 $n$ 是 Bessie 的牛棚; 地点 $1$ 是池塘。很快，Bessie 厌倦了一直走同一条路。所以她想走不同的路，更明确地讲，她想找出 $k$ 条不同的路径。为了避免过度劳累,她想使这 $k$ 条路经为最短的 $k$ 条路径。请帮助 Bessie 找出这 $k$ 条最短路径的长度。

输入格式

• 第 $1$ 行: $3$ 个数: $n,m,k$

• 第 $2\sim m+1$ 行：第 $i+1$ 行包含3个数 $x_i,y_i,d_i$，表示一条下坡的路.

输出格式

• 第 $1\sim 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

数据规模与约定

对于 $100\%$ 的数据，$1 \leq N \leq 1000$，$1 \leq m \leq 1\times10^4$，$1 \leq k \leq 100$，$1 \leq y_i < x_i \leq n$，$1 \leq d_i \leq 1\times10^6$。

提示

路径分别为 $(5-1)$，$(5-3-1)$，$(5-2-1)$，$(5-3-2-1)$，$(5-4-3-1)$， $(5-4-3-2-1)$。

题目来源

Usaco 2008 Mar Gold