7575: [CSES Problem Set] Flight Routes
[Creator : ]
Description
Your task is to find the $k$ shortest flight routes from Syrjälä to Metsälä. A route can visit the same city several times.
Note that there can be several routes with the same price and each of them should be considered (see the example).
Note that there can be several routes with the same price and each of them should be considered (see the example).
Input
The first input line has three integers $n, m, k$: the number of cities, the number of flights, and the parameter $k$. The cities are numbered $1,2,\ldots,n$. City $1$ is Syrjälä, and city $n$ is Metsälä.
After this, the input has mm lines describing the flights. Each line has three integers $a, b, c$: a flight begins at city $a$, ends at city $b$, and its price is $c$. All flights are one-way flights.
You may assume that there are at least $k$ distinct routes from Syrjälä to Metsälä.
After this, the input has mm lines describing the flights. Each line has three integers $a, b, c$: a flight begins at city $a$, ends at city $b$, and its price is $c$. All flights are one-way flights.
You may assume that there are at least $k$ distinct routes from Syrjälä to Metsälä.
Output
Print $k$ integers: the prices of the $k$ cheapest routes sorted according to their prices.
Constraints
$2≤n≤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$
$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$
Sample 1 Input
4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1
Sample 1 Output
4 4 7
The cheapest routes are $1 \rightarrow 3 \rightarrow 4$ (price 4), $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ (price 4) and $1 \rightarrow 2 \rightarrow 4$ (price 7).