Đến du lịch ở thành phố Dream Land, Nam may mắn được công ty lữ hành tặng k vé xe buýt miễn phí để đi thăm quan thành phố này. Mỗi vé xe chỉ được sử dụng một lần và có thể sử dụng cho bất kỳ tuyến xe buýt nào trong thành phố. Thành phố có n nút giao thông được đánh số thừ 1 đến n và m tuyến xe buýt hai chiều. Mỗi cặp nút giao thông i, j có không quá một chuyến xe buýt hai chiều, nếu có thể đi từ nút i đến nút j (hoặc từ nút j đến nút i) với giá vé là cij=cji đồng. Xuất phát từ nút giao thông s, Nam muốn di chuyển đến nút giao thông t và Nam luôn lựa chọn đường đi với chi phí ít nhất.
Ví dụ: thành phố có 5 nút giao thông và 6 tuyến xe buýt:

Tuyến 1: 1-2 giá vé 10 đồng;
Tuyến 2: 2-5 giá vé 10 đồng;
Tuyến 3: 1-4 giá vé 3 đồng;
Tuyến 4: 3-4 giá vé 5 đồng;
Tuyến 5: 3-5 giá vé 3 đồng;
Tuyến 6: 1-3 giá vé 20 đồng;
Xuất phát từ nút 1 đến nút 5, đi theo hành trình 1 -> 4 -> 3 -> 5 hết 11 đồng là đường đi với chi phí ít nhất. Tuy nhiên, nếu Nam sử dụng 1 vé xe miễn phí thì đường đi 1 -> 3 -> 5 hết 3 đồng là ít nhất (vé xe miễn phí được sử dụng tại tuyến 1 – 3).
Yêu cầu: Cho biết các tuyến xe buýt với giá vé tương ứng và các giá trị s, t, k. Hãy tính chi phí ít nhất để đi từ nút giao thông s đến nút giao thông t mà không sử dụng quá k vé xe miễn phí.

Input

• Dòng đầu tiên ghi năm số nguyên dương n, m, k, s, t; 1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5 và 1 ≤ k ≤ 5.
• m dòng sau, mỗi dòng 3 số nguyên i, j, cij mô tả có tuyến xe buýt i – j hết cij đồng.

Output

-Một số duy nhất là chi phí ít nhất để đi từ nút giao thông s đến nút giao thông t mà không sử dụng quá k vé xe miễn phí.

Example

5 6 1 1 5
1 2 10
2 5 10
1 4 3
3 4 5
3 5 3
1 3 20  

3