Bình đang thiết kế hệ thống dẫn nước tưới tiêu cho một trang trại rộng lớn. Hệ thống gồm \(N\) trạm bơm (đánh số từ 1 đến \(N\)) và \(M\) ống dẫn nước một chiều. Mỗi ống dẫn có một dung lượng tối đa (lít/giây).

Trạm bơm số 1 là nguồn cấp nước chính, trạm bơm số \(N\) là điểm tập kết cuối cùng. Nước chảy từ trạm 1 qua mạng lưới ống dẫn đến trạm \(N\).

Hãy tính lượng nước tối đa (lít/giây) có thể vận chuyển từ trạm bơm số 1 đến trạm bơm số \(N\).

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

• Dòng đầu chứa bốn số nguyên \(N\), \(M\), \(S\), \(T\) (\(2 \le N \le 300\), \(1 \le M \le 20000\), \(S \neq T\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\), \(c\) (\(1 \le u, v \le N\), \(1 \le c \le 10^4\)) mô tả ống dẫn 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 nước tối đa có thể vận chuyển.

Ví dụ

Input:

4 5 1 4
1 2 40
1 3 20
2 3 10
2 4 30
3 4 20

Output:

50