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.

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.

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\).