5337. 航班路线（Flight Routes）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 你的任务是找出从西尔贾拉（Syrjälä）到迈赛拉（Metsälä）的 $k$ 条最短航线。航线可以多次经过同一个城市。 请注意，可能存在多条价格相同的不同航线，它们都应该被计算在内。 ## 输入格式 第一行三个整数 $n$、$m$ 和 $k$，分别表示城市数量、航班数量和参数 $k$。城市编号为 $1, 2, \dots, n$，其中城市 $1$ 是西尔贾拉，城市 $n$ 是迈赛拉。 接下来 $m$ 行，每行三个整数 $a$、$b$ 和 $c$，表示一条从 $a$ 到 $b$ 的单向航班，价格为 $c$。 ## 输出格式 输出 $k$ 个整数，表示前 $k$ 条最便宜航线的值，按价格从小到大排序。 ## 输入输出样例 ### 输入 #1 ``` 4 6 3 1 2 1 1 3 3 2 3 2 2 4 6 3 2 8 3 4 1 ``` ### 输出 #1 ``` 4 4 7 ``` ## 说明/提示 ### 数据规模与约定 - $2 \le n \le 10^5$ - $1 \le m \le 2 \cdot 10^5$ - $1 \le a, b \le n$ - $1 \le c \le 10^9$ - $1 \le k \le 10$