Hệ thống đường ống dẫn khí đốt gồm \(N\) trạm trung chuyển và \(M\) ống dẫn một chiều. Mỗi trạm trung chuyển chỉ có thể xử lý tối đa một lượng khí nhất định (m³/giờ) do giới hạn công suất máy nén.

Nguồn khí được bơm vào trạm \(S\) và cần ra đến trạm \(T\). Hãy tính lượng khí tối đa có thể vận chuyển, biết rằng mỗi trạm có dung lượng riêng và mỗi ống dẫn cũng có dung lượng riêng.

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

• Dòng đầu chứa bốn số nguyên \(N\), \(M\), \(S\), \(T\) (\(2 \le N \le 500\), \(1 \le M \le 10000\), \(S \neq T\)).
• Dòng thứ hai chứa \(N\) số nguyên \(cap_i\) (\(1 \le cap_i \le 10^4\)) là dung lượng của trạm thứ \(i\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\), \(c\) (\(1 \le c \le 10^4\)) mô tả ống từ \(u\) đến \(v\) với dung lượng \(c\).

Định dạng đầu ra

• Một số nguyên duy nhất là lượng khí tối đa.

Ví dụ

Input:

4 4 1 4
10 5 8 6
1 2 10
2 4 10
1 3 10
3 4 10

Output:

11