Hãng hàng không giá rẻ phục vụ các chuyến bay giữa \(N\) thành phố thông qua \(M\) đường bay một chiều. Để kích cầu du lịch, một số chặng bay có chính sách trợ giá âm (hành khách được hoàn lại tiền).

Tèo muốn đi từ thành phố \(S\) tới thành phố \(T\) bằng máy bay với điều kiện hành trình không được quá \(K\) chặng bay (tức là đi qua tối đa \(K\) cạnh). Hãy tìm chi phí di chuyển tối thiểu thỏa mãn yêu cầu này.

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

• Dòng đầu chứa năm số nguyên \(N\), \(M\), \(K\), \(S\), \(T\) (\(1 \le N \le 1000\), \(0 \le M \le 2000\), \(1 \le K \le 100\), \(1 \le S, T \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 chi phí tối thiểu thỏa mãn điều kiện. Nếu không có hành trình nào hợp lệ, 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 1 1 3
1 2 5
2 3 5
1 3 15

Output:

15

Giải thích: Hành trình \(1 \to 2 \to 3\) có chi phí 10 nhưng cần 2 chặng bay (lớn hơn giới hạn \(K=1\)). Hành trình hợp lệ duy nhất là chặng bay thẳng \(1 \to 3\) với chi phí 15.