영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
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).
Input
The first input line has three integers n, m, and k: the number of cities, the number of flights, and the parameter k. The cities are numbered 1,2,…,n. City 1 is Syrjälä, and city n is Metsälä.
After this, the input has m lines describing the flights. Each line has three integers a, b, and 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 ≤ m ≤ 2 · 10^5
- 1 ≤ a,b ≤ n
- 1 ≤ c ≤ 10^9
- 1 ≤ k ≤ 10
Example
Explanation: The cheapest routes are 1 → 3 → 4 (price 4), 1 → 2 → 3 → 4 (price 4) and 1 → 2 → 4 (price 7).
예제
예제 1
4 6 3 1 2 1 1 3 3 2 3 2 2 4 6 3 2 8 3 4 1
4 4 7