Nhiệm vụ của bạn là tìm ra $k$ đường đi có tổng chi phí nhỏ nhất từ thủ đô Syrjälä (thành phố $1$) đến thành phố Metsä (thành phố $n$). Một đường đi hợp lệ hoàn toàn có thể thăm lại một thành phố hoặc đi qua cùng một chuyến bay nhiều lần.

Dữ liệu vào (Input):

• Dòng đầu tiên chứa ba số nguyên dương $n,m$ và $k$: lần lượt là số lượng thành phố, số lượng chuyến bay và tham số $k$. Các thành phố được đánh số thứ tự từ $1$ đến $n$.
• $m$ dòng tiếp theo mô tả danh sách các chuyến bay. Mỗi dòng chứa ba số nguyên $a,b$ và $c$ với ý nghĩa: có một chuyến bay một chiều xuất phát từ thành phố $a$ đến thành phố $b$ với chi phí (giá vé) là $c$.

Dữ liệu ra (Output):

• In ra $k$ số nguyên là chi phí của $k$ đường đi rẻ nhất từ thành phố $1$ đến thành phố $n$, được sắp xếp theo thứ tự không giảm (tăng dần).

Giới hạn (Constraints):

• $2\le n\le {10}^5$
• $1\le m\le 2·{10}^5$
• $1\le a,b\le n$
• $1\le c\le {10}^9$
• $1\le k\le 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