Maximum Flow in a Network Graph

Given a directed network graph with capacities on its edges, a source vertex s and a sink vertex t, compute the maximum flow from s to t. The flow on each edge cannot exceed its capacity. Formally, if f(u,v) represents the flow from vertex u to vertex v, then the maximum flow is defined as:

$$\text{max\_flow} = \sum_{(s,v) \in E} f(s,v)$$

subject to the capacity constraints and the flow conservation property for all intermediate vertices.

inputFormat

The first line contains four integers n m s t, where n is the number of vertices, m is the number of edges, s is the source vertex and t is the sink vertex. Vertices are numbered from 1 to n. Each of the following m lines contains three integers u v c representing a directed edge from vertex u to vertex v with capacity c.

outputFormat

Output a single integer which is the maximum flow from the source s to the sink t in the given network graph.

sample

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

50