Nhiệm vụ của bạn là tìm \(k\) lộ trình bay ngắn nhất từ Syrjälä đến Metsälä. Một lộ trình có thể đi qua một thành phố vài lần.

Lưu ý rằng có thể có một số lộ trình với cùng một mức giá và mỗi lộ trình nên được xét (xem ví dụ).

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\), và \(k\): số lượng thành phố, chuyến bay, và tham số \(k\). Các thành phố được đánh số \(1, 2, \ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Metsälä.
• Sau này, có \(m\) dòng 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ại thành phố \(a\), kết thúc tại thành phố \(b\), và giá của nó là \(c\). Tất cả các chuyến bay đều là chuyến bay một chiều.
• Bạn có thể giả định rằng có ít nhất \(k\) lộ trình phân biệt từ Syrjälä đến Metsälä.

Constraints

• \(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\)

Output

• In \(k\) số nguyên: giá của \(k\) tuyến đường rẻ nhất được sắp xếp theo giá của chúng.

Example

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

4 4 7