You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1196 题。

题目描述

你的任务是找出从 Syrjälä 到 Metsälä 的 $k$ 条最短航班路线。一个路线可以多次经过同一个城市。

注意：可能存在多个价格相同的路线，每条这样的路线都应该被考虑（请参考示例）。

输入格式

第一行包含三个整数 $n$，$m$，和 $k$：分别表示城市的数量、航班的数量和需要找到的最短路线的数量 $k$。城市编号为 $1,2,…,n$，其中城市 $1$ 是 Syrjälä，城市 $n$ 是 Metsälä。

接下来的 $m$ 行，每行描述一条航班，包含三个整数 $a$，$b$，和 $c$：表示从城市 $a$ 到城市 $b$ 的一条单向航班，航班的价格为 $c$。

你可以假设从 Syrjälä 到 Metsälä 至少有 $k$ 条不同的路线。

输出格式

输出 $k$ 个整数：表示从 Syrjälä 到 Metsälä 的 $k$ 条最便宜路线的价格，并按照价格从小到大排序。

样例

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

4 4 7

样例1解释

最便宜的三条路线分别是：

1. $1 → 3 → 4$（价格为 $4$）
2. $1 → 2 → 3 → 4$（价格为 $4$）
3. $1 → 2 → 4$（价格为 $7$）

因此，输出价格分别为 $4$、$4$ 和 $7$。

说明/提示

$2 \leq n \leq 10^5$；

$1 \leq m \leq 2 \cdot 10^5$；

$1 \leq a,b \leq n$；

$1 \le c \le 10^9$；

$1 \leq k \leq 10$。