K đường đi ngắn nhất

Cho đồ thị vô hướng gồm \(N\) đỉnh, \(M\) cạnh có trọng số. Một hành trình từ đỉnh \(1\) đến đỉnh \(N\) là một dãy các cạnh nối tiếp nhau bắt đầu tại đỉnh \(1\) và kết thúc tại đỉnh \(N\); hành trình được phép đi qua một đỉnh hoặc một cạnh nhiều lần (kể cả đi qua đỉnh \(N\) rồi quay lại). Độ dài của hành trình là tổng độ dài các cạnh trên hành trình (cạnh đi qua nhiều lần được tính nhiều lần).

Hãy tìm \(k\) giá trị độ dài khác nhau nhỏ nhất có thể của một hành trình từ đỉnh \(1\) đến đỉnh \(N\) (nhiều hành trình có cùng độ dài chỉ được tính một lần).

Input

• Dòng \(1\): ba số nguyên \(N, M, k\) (\(2 \le N \le 10^3\); \(0 \le M \le 10^4\); \(1 \le k \le 100\)).
• \(M\) dòng tiếp theo, mỗi dòng ghi \(3\) số nguyên dương \(a, b, d\) cho biết có đường đi hai chiều giữa \(a\) và \(b\) (\(a \ne b\)) có độ dài bằng \(d\) (\(1 \le d \le 100000\)).

Output

• Nếu không tồn tại hành trình nào từ \(1\) đến \(N\), in ra \(-1\).
• Ngược lại, in ra trên một dòng \(k\) số nguyên \(d_1 < d_2 < \cdots < d_k\), với \(d_i\) là độ dài ngắn thứ \(i\) (khi đã tồn tại một hành trình thì luôn có vô số độ dài khác nhau, vì có thể đi đi lại lại trên một cạnh).

Scoring

• Có \(30\%\) số test tương ứng \(30\%\) số điểm có \(N, k \le 12\).

Sample Input 1

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

Sample Output 1

10 11

Sample Input 2

2 1 3
1 2 1

Sample Output 2

1 3 5

Notes

• Ví dụ \(1\): ngắn nhất là \(1 \to 2 \to 4\) hoặc \(1 \to 3 \to 4\) cùng độ dài \(10\) (chỉ tính một lần); ngắn nhì là \(1 \to 2 \to 3 \to 4\) có độ 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\).