Bình lái xe điện đi từ thành phố \(S\) đến thành phố \(T\). Bình điện của xe có dung lượng tối đa \(C\) đơn vị năng lượng. Khi đi qua một con đường một chiều nối \(u\) và \(v\) có chiều dài \(w\), xe sẽ tiêu thụ đúng \(w\) đơn vị năng lượng.

Thành phố có \(N\) đỉnh, tại một số đỉnh có trạm sạc điện. Khi dừng tại trạm sạc ở đỉnh \(u\), Bình có thể mua thêm năng lượng sạc vào bình với đơn giá là \(P[u]\) đồng mỗi đơn vị năng lượng. Dung lượng bình điện không thể vượt quá \(C\). Ban đầu tại \(S\), xe có \(0\) đơn vị năng lượng trong bình (phải sạc năng lượng tại \(S\) để có thể đi tiếp).

Hãy tìm chi phí mua năng lượng tối thiểu để Bình lái xe đi từ \(S\) đến \(T\).

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

• Dòng đầu chứa năm số nguyên \(N, M, C, S, T\) (\(1 \le N \le 1000\), \(0 \le M \le 2000\), \(1 \le C \le 100\), \(1 \le S, T \le N\)).
• Dòng thứ hai chứa \(N\) số nguyên \(P[1], P[2], \dots, P[N]\) (\(1 \le P[i] \le 100\)). Nếu \(P[i] = 0\), tại đỉnh \(i\) không có trạm sạc điệ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\), \(1 \le w \le C\)) mô tả con đường một chiều nối \(u\) sang \(v\) tiêu hao \(w\) năng lượng.

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí tiền mua năng lượng tối thiểu. Nếu không thể đi tới đích, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

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

Output:

50

(Giải thích ví dụ: Trạm sạc 1 giá 5, trạm sạc 2 giá 10. Đi 1 -> 2 -> 3. Tại 1 sạc 10 đơn vị (tốn 50 đồng). Đến 2 còn 5 đơn vị. Đi tiếp 2 -> 3 đến 3 còn 0 đơn vị. Tổng chi phí là 50).