Cho đồ thị vô hướng gồm ~N~ đỉnh, ~M~ cạnh. Bạn hãy tìm độ dài ~k~ đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~N~.

Các độ dài các đường đi này là khác nhau.

Input

• Dòng đầu tiên chứa 3 số nguyên ~N, M, k~ với điều kiện: ~ N \leq 1000;\quad M \leq 10000;\quad k \leq 100 ~

• ~M~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên dương ~a, b, d~ tương ứng là có đường đi hai chiều giữa ~a~ và ~b~ có độ dài bằng ~d~: ~ 1 \leq d \leq 100000 ~

Output

• In ra ~k~ số nguyên ~d_1, d_2, \ldots, d_k~ với ~d_i~ là độ dài đường đi ngắn thứ ~i~.
• Nếu không tồn tại đường đi, in ra ~-1~ tại vị trí đó.

Scoring

~30\%~ số điểm có ~n, k \leq 12~

Ví dụ

Input

4 6 2
1 2 5
1 3 5
2 3 1
2 4 5
3 4 5
1 4 13

Output

10 11

Input

2 1 3
1 2 1

Output

1 3 5

Giải thích ví dụ:

Ví dụ 1:

• Ngắn nhất: ~1 \to 2 \to 4~ hoặc ~1 \to 3 \to 4~ độ dài ~10~.
• Ngắn nhì: ~1 \to 2 \to 3 \to 4~: độ dài ~11~.

Ví dụ 2:

• Ngắn nhất: ~1 \to 2~, độ dài ~1~.
• Ngắn nhì: ~1 \to 2 \to 1 \to 2~, độ dài ~3~.
• Ngắn ba: ~1 \to 2 \to 1 \to 2 \to 1 \to 2~, độ dài ~5~.