Nhiệm vụ của bạn là tìm k đường bay ngắn nhất từ thành phố 1 đến thành phố n. Một tuyến đường có thể ghé thăm cùng một thành phố nhiều lần.

Input

Dòng đầu tiên chứa 3 số nguyên n, m, k: số thành phố, số con đường và k. Các thành phố được đánh số 1,2,...,n.

Sau đó, đầu vào có m dòng mô tả các con đường. Mỗi dòng có ba số nguyên u, v và w: con đường bắt đầu ở thành phố u, kết thúc ở thành phố v và giá của nó là w. Tất cả các con đường đều là một chiều.

Output

In ra 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.

Hạn chế

~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~

Examples

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: Các tuyến rẻ nhất là:

1 -> 3 -> 4 (chi phí 4)

1 -> 2 -> 3 -> 4 (chi phí 4)

1 -> 2 -> 4 (chi phí 7).