Trong lý thuyết đồ thị, mạng luồng là một đồ thị có hướng, trong đó mỗi cạnh có một độ thông qua và một giá trị luồng. Lượng luồng trên mỗi cạnh không được vượt quá độ thông qua của cạnh đó. Lượng luồng đi vào một đỉnh phải bằng lượng luồng đi ra khỏi nó, trừ khi đó là đỉnh nguồn (có nhiều lượng luồng đi ra hơn), hay đỉnh thu (có nhiều lượng luồng đi vào hơn).

Mạng luồng có thể dùng để mô hình hóa hệ thống đường giao thông, dòng chảy của chất lỏng trong ống, dòng điện trong mạch, hay bất kỳ bài toán nào tương tự khi có sự di chuyển trong một mạng các nút.

Yêu cầu

Cho một mạng luồng, hãy tìm giá trị luồng cực đại từ đỉnh phát \(s\) đến đỉnh thu \(t\).

Input

• Dòng đầu tiên chứa 4 số nguyên dương \(n, m, s, t\) (\(2 \le n \le 1000\)) tương ứng là số đỉnh, số cạnh của đồ thị, chỉ số của đỉnh phát và đỉnh thu.
• Trong \(m\) dòng tiếp theo, mỗi dòng có dạng ba số \(u, v, c\) cách nhau ít nhất một dấu cách thể hiện có cung \((u, v)\) trong mạng với khả năng thông qua là \(c\) (\(1 \le c \le 10^9\)).

Output

• In ra một số duy nhất là giá trị của luồng cực đại trên mạng.

Example

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

9