Tèo đang vận hành một mạng lưới đường ống dẫn dầu quy mô lớn. Mạng lưới gồm \(N\) trạm trung chuyển và \(M\) ống dẫn một chiều, mỗi ống có giới hạn lưu lượng tối đa.

Trạm \(1\) là nơi khai thác dầu thô, trạm \(N\) là nhà máy lọc dầu. Dầu được bơm từ trạm \(1\) qua hệ thống đường ống đến trạm \(N\).

Hãy tính lưu lượng dầu tối đa (thùng/giờ) từ trạm \(1\) đến trạm \(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 1000\), \(1 \le M \le 50000\), \(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ưu lượng dầu tối đa.

Ví dụ

Input:

5 7 1 5
1 2 10
1 3 5
2 3 15
2 4 10
3 4 10
3 5 5
4 5 10

Output:

20