Maximum Flow

You are given \(n\) nodes and \(m\) directed edges. Each edge has an associated capacity. Your task is to compute the maximum flow from the start node \(s\) to the target node \(t\).

Note: The graph may contain multiple edges (i.e. parallel edges) between the same pair of nodes.

inputFormat

The first line contains four integers: \(n\), \(m\), \(s\), and \(t\), where \(n\) is the number of nodes, \(m\) is the number of edges, \(s\) is the source node, and \(t\) is the target node. Nodes are numbered from 1 to \(n\).

The following \(m\) lines each contain three integers \(u\), \(v\), and \(c\), representing a directed edge from node \(u\) to node \(v\) with capacity \(c\). Multiple edges between the same two nodes are allowed.

outputFormat

Output a single integer, the maximum flow from \(s\) to \(t\).

sample

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

50