Các Tuyến Bay

Có $n$ thành phố và $m$ chuyến bay một chiều. Tìm $k$ đường đi có chi phí nhỏ nhất từ thành phố $1$ đến thành phố $n$ (đường đi có thể đi qua một thành phố nhiều lần, các đường có chi phí bằng nhau được tính riêng).

Dữ liệu vào

• Dòng 1: ba số nguyên $n$, $m$, $k$.
• $m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$, $b$, $c$ — chuyến bay từ $a$ đến $b$ với chi phí $c$.

Dữ liệu ra

In $k$ số nguyên — chi phí của $k$ đường đi ngắn nhất theo thứ tự tăng dần.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le m\le 2\times {10}^5$
• $1\le k\le 10$
• $1\le c\le {10}^9$
• Đảm bảo tồn tại ít nhất $k$ đường đi từ $1$ đến $n$.

Ví dụ