K lộ trình rẻ nhất

Bối cảnh và bài toán

Hệ thống cần liệt kê k chi phí nhỏ nhất của các lộ trình từ 1 tới n. Một lộ trình có thể đi qua cùng một nút nhiều lần và các lộ trình có cùng chi phí đều được tính riêng.

Yêu cầu

In k chi phí nhỏ nhất theo thứ tự không giảm.

Input

Dòng đầu n, m, k; tiếp theo m cạnh có hướng u, v, w.

Output

In k số trên một dòng.

Ràng buộc

• 2 <= n <= 10^5
• 1 <= m <= 2*10^5
• 1 <= k <= 10
• 1 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

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

Output

4 4 7

Giải thích. Heap mở rộng các walk theo tổng chi phí tăng dần; nút đích được ghi nhận nhiều lần tới khi đủ k kết quả.

Ví dụ 2

Input

2 2 2
1 2 5
1 2 7

Output

5 7

Giải thích. Heap mở rộng các walk theo tổng chi phí tăng dần; nút đích được ghi nhận nhiều lần tới khi đủ k kết quả.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Flight Routes. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.