Mạng thám hiểm lòng đất gồm \(N\) hang động và M lối đi một chiều có trọng số (có thể âm). Để đo đạc chính xác địa chấn, robot thám hiểm cần di chuyển từ hang động nguồn S đến các hang động khác bằng cách đi qua đúng \(K\) lối đi.

Hãy tính chi phí di chuyển ngắn nhất từ \(S\) đến mọi hang động thứ i sử dụng đúng \(K\) bước.

Định dạng đầu vào

• Dòng đầu chứa bốn số nguyên \(N\), M, K, S (\(1 \le N \le 1000, 0 \le M \le 2000, 1 \le K \le 100, 1 \le S $\le N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w (\(1 \le u, v \le N, -1000 \le w $\le 1000\)).

Định dạng đầu ra

• In ra \(N\) dòng, dòng thứ i là khoảng cách ngắn nhất từ S tới i sau đúng K bước. Nếu không thể đến được sau đúng \(K\) bước, in ra impossible.

Ví dụ

Input:

3 3 2 1
1 2 5
2 3 10
1 3 12

Output:

impossible
impossible
15

Giải thích:

• Nút 1: Không thể quay lại chính nó sau đúng 2 bước.
• Nút 2: Không thể đi đến sau đúng 2 bước (chỉ có đường \(1 \to 2\) dài 1 bước).
• Nút 3: Đường đi \(1 \to 2 \to 3\) có độ dài đúng 2 bước và chi phí \(5 + 10 = 15\).

Ràng buộc

• Subtask 1 (40% số điểm): \(N \le 100, K \le 10.\)
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.