Tuyến đường bay

Trong một dự án về giao thông, FullHouse Dev được giao nhiệm vụ phân tích các tuyến đường bay giữa các thành phố. Họ cần tìm ra \(k\) tuyến đường bay có chi phí thấp nhất từ thành phố Syrjälä đến thành phố Metsälä.

Bài toán

FullHouse Dev cần tìm \(k\) tuyến đường bay ngắn nhất từ Syrjälä đến Metsälä. Một tuyến đường có thể đi qua cùng một thành phố nhiều lần. Lưu ý rằng có thể có nhiều tuyến đường có cùng chi phí và mỗi tuyến đường đều cần được xem xét.

INPUT FORMAT:

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\): số lượng thành phố, số lượng chuyến bay và tham số \(k\). Các thành phố được đánh số từ \(1\) đến \(n\). Thành phố 1 là Syrjälä và thành phố \(n\) là Metsälä.
• \(m\) dòng tiếp theo mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): chuyến bay bắt đầu từ thành phố \(a\), kết thúc tại thành phố \(b\) và có chi phí là \(c\). Tất cả các chuyến bay đều là một chiều.

OUTPUT FORMAT:

• In ra \(k\) số nguyên: chi phí của \(k\) tuyến đường rẻ nhất được sắp xếp theo thứ tự tăng dần.

Ràng buộc:

• \(2 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)
• \(1 \leq k \leq 10\)

Ví dụ

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

Các tuyến đường rẻ nhất là:

• \(1 \rightarrow 3 \rightarrow 4\) (chi phí 4)
• \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\) (chi phí 4)
• \(1 \rightarrow 2 \rightarrow 4\) (chi phí 7)