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

Ràng buộc & Subtasks