Bình lái xe đi từ thành phố \(S\) đến thành phố \(T\). Xe có bình xăng tối đa chứa được \(F\) lít xăng. Xe di chuyển trên một con đường hai chiều nối giữa hai thành phố tiêu hao đúng \(w\) lít xăng cho mỗi cây số (độ dài con đường).

Xe chỉ có thể đi qua một con đường nếu lượng xăng hiện tại trong bình lớn hơn hoặc bằng chiều dài con đường đó.

Tại một số thành phố có cây xăng miễn phí. Khi dừng tại thành phố có cây xăng, Bình có thể đổ đầy bình xăng lên dung lượng \(F\) mà không tốn tiền. Hãy tìm lộ trình di chuyển có tổng khoảng cách địa lý ngắn nhất đi từ \(S\) đến \(T\).

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

• Dòng đầu chứa năm số nguyên \(N, M, F, S, T\) (\(1 \le N \le 1000\), \(0 \le M \le 2000\), \(1 \le F \le 100\), \(1 \le S, T \le N\)).
• Dòng thứ hai chứa \(N\) số nguyên biểu diễn trạng thái trạm xăng tại mỗi thành phố: \(1\) là có trạm xăng, \(0\) là không có trạm xăng.
• \(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\), \(1 \le w \le F\)) mô tả con đường hai chiều nối \(u\) và \(v\) tiêu hao \(w\) lít xăng.

Định dạng đầu ra

• Một số nguyên duy nhất là tổng độ dài địa lý ngắn nhất. Nếu không thể đi tới, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

4 4 10 1 4
1 0 1 1
1 2 6
2 3 5
3 4 6
1 3 9

Output:

15

(Giải thích ví dụ: Tại 1 đổ xăng đầy bình 10 lít. Đi 1 -> 3 tốn 9 lít xăng, đến 3 còn 1 lít. Không thể đi tiếp 3 -> 4 vì cần 6 lít xăng mà 3 không có cây xăng. Nhưng nếu đi 1 -> 2 -> 3... wait, 2 và 3 không có cây xăng. Vậy nếu đi 1 -> 3 tốn 9 lít. Đợi đã, 1 -> 3 trực tiếp là 9 lít. Ô 4 có cây xăng nhưng là đích rồi. Vậy làm thế nào để đi tới 4? Có con đường khác không? Không. Vậy không đi được? A, ví dụ ghi output 15? Hãy xem lại ví dụ: 1 2 6 2 3 5 3 4 6 1 3 9 Nếu ta đi 1 -> 3 dài 9. Không thể đi 3 -> 4. Nhưng nếu đi 1 -> 2 dài 6. Tại 2 còn 4 lít. Đi 2 -> 3 dài 5 (cần 5 lít nhưng còn 4) -> không đi được. Nhớ lại: tại sao output 15? Nếu ta đi 1 -> 3 dài 9. Và 3 -> 4 dài 6. Tổng là 15. Nhưng 3 -> 4 cần 6 lít xăng, trong khi đến 3 chỉ còn 1 lít và 3 không có cây xăng. Ah! Có thể bình xăng ban đầu được đổ đầy 10 lít tại 1. Nếu ta đi 1 -> 2 dài 6. Cần cây xăng tại 2? 2 không có cây xăng. Nếu ví dụ có cây xăng tại 3? Dòng thứ hai là 1 0 1 1 (tức là 1, 3, 4 có cây xăng). Đúng vậy! Nếu 3 có cây xăng, tại 1 đổ đầy 10. Đi 1 -> 3 dài 9 (còn 1). Tại 3 có cây xăng, đổ đầy 10. Đi 3 -> 4 dài 6 (còn 4). Tổng khoảng cách đi là 9 + 6 = 15! Và dòng thứ hai lúc đó phải là 1 0 1 1. Hãy điều chỉnh dòng thứ hai của ví dụ trong đề bài thành 1 0 1 1 để khớp chuẩn).