#T2093. 飞行路线(Flight Routes)

飞行路线(Flight Routes)

链接: https://cses.fi/problemset/task/1195

板块: Graph Algorithms

时限: 1.00 s | 内存: 512 MB

题目描述

你的任务是找出从 Syrjälä 到 Metsälä 的 kk 条最短飞行路线。一条路线可以多次经过同一座城市。

注意可能存在多条价格相同的路线,每一条都应被计入(见样例)。

输入

第一行输入包含三个整数 nn、mm 和 kk:城市数量、航班数量、参数 kk。城市编号为 1,2,…,n1,2,\ldots,n。城市 1 是 Syrjälä,城市 nn 是 Metsälä。

之后有 mm 行描述航班。每行包含三个整数 aa、bb 和 cc:航班从城市 aa 出发,抵达城市 bb,价格为 cc。所有航班均为单向航班。

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

输出

输出 kk 个整数:按价格排序的 kk 条最便宜路线的价格。

数据范围

2≤n≤1052 \le n \le 10^5 1≤m≤2⋅1051 \le m \le 2 \cdot 10^5 1≤a,b≤n1 \le a,b \le n 1≤c≤1091 \le c \le 10^9 1≤k≤101 \le k \le 10

样例输入

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→3→41 \rightarrow 3 \rightarrow 4(价格 44)、1→2→3→41 \rightarrow 2 \rightarrow 3 \rightarrow 4(价格 44)和 1→2→41 \rightarrow 2 \rightarrow 4(价格 77)。