Maximum Flow using the Edmonds-Karp Algorithm

You are given a directed network graph with n vertices and m edges. Each edge is specified by three integers u, v and c representing an edge from vertex u to vertex v with capacity c. Your task is to compute the maximum flow from the source vertex 1 to the sink vertex n using the Edmonds-Karp algorithm.

The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method that uses breadth-first search (BFS) to select the shortest augmenting paths. The algorithm terminates when no more augmenting paths can be found. Mathematically, if f represents the flow and c the capacities, you need to maximize:

$$\text{max flow} = \sum_{v \in V} f(1,v)$$

subject to the capacity constraints and the flow conservation constraints.

inputFormat

The first line contains two integers n and m representing the number of vertices and edges respectively. Each of the following m lines contains three integers u, v, and c which denotes there is an edge from vertex u to vertex v with capacity c.

You should read the input from standard input (stdin).

outputFormat

Output a single integer representing the maximum flow from vertex 1 to vertex n on standard output (stdout).

## sample

4 5
1 2 100
1 3 100
2 3 1
2 4 100
3 4 100

200

</p>