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 \cdot 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