Các tuyến bay (Flight Routes)

Nguồn: CSES Problem Set

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ thành phố và $m$ chuyến bay một chiều.

Hãy tìm chi phí của $k$ tuyến bay rẻ nhất từ thành phố $1$ đến thành phố $n$.

Một tuyến được phép đi qua cùng một thành phố nhiều lần. Nhiều tuyến khác nhau có thể có cùng chi phí và vẫn phải được tính riêng.

Đề bảo đảm tồn tại ít nhất $k$ tuyến từ thành phố $1$ đến thành phố $n$.

Input

Dòng đầu chứa ba số nguyên $n,m,k$.

Trong $m$ dòng tiếp theo, mỗi dòng chứa $a,b,c$, mô tả một chuyến bay một chiều từ $a$ đến $b$ có giá $c$.

Output

In $k$ số nguyên theo thứ tự không giảm: chi phí của $k$ tuyến rẻ nhất từ thành phố $1$ đến thành phố $n$.

Subtask

Trong tất cả các Subtask: $2\le n\le10^5$; $1\le m\le2\cdot10^5$; $1\le k\le10$; $1\le a,b\le n$; $1\le c\le10^9$; tồn tại ít nhất $k$ tuyến từ $1$ đến $n$.

• Subtask 1 — 10%: $k=1$.
• Subtask 2 — 20%: Mọi chuyến bay $a\to b$ đều thỏa $a<b$.
• Subtask 3 — 30%: $n\le300$; $m\le2000$; $k\le10$.
• Subtask 4 — 40%: Không có điều kiện bổ sung.

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

Ba tuyến rẻ nhất có chi phí lần lượt là $4,4,7$. Hai tuyến đầu khác nhau nhưng có cùng tổng chi phí nên đều được tính.