Maximum Commuter Flow

You are given a network of intersections connected by undirected streets. Each street connects two intersections and has a capacity representing the maximum number of commuters that can simultaneously use that street. Given a starting intersection \(S\) and a destination intersection \(T\), determine the maximum number of commuters that can travel from \(S\) to \(T\) when the streets are used optimally.

Formally, let \(N\) be the total number of intersections and \(M\) be the total number of streets. Each street is represented by a triplet \((u, v, c)\) where \(u\) and \(v\) are the intersections connected by the street and \(c\) is its capacity. The network is undirected, so each street can be used in both directions.

Your task is to compute the maximum flow from \(S\) to \(T\) in this network. The maximum flow is the greatest amount that can be sent from the source to the sink without violating any street capacity constraints.

inputFormat

The first line contains four integers \(N\), \(M\), \(S\), and \(T\), where \(N\) is the number of intersections, \(M\) is the number of streets, \(S\) is the starting intersection, and \(T\) is the destination intersection.

The following \(M\) lines each contain three integers \(u\), \(v\), and \(c\), representing an undirected street between intersections \(u\) and \(v\) with capacity \(c\).

Input is provided via standard input (stdin).

outputFormat

Output a single integer representing the maximum number of commuters that can be routed from intersection \(S\) to \(T\).

Output should be written to standard output (stdout).

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

50