Competitions

# Maximum flow and matchings

# Maximum flow

Find the maximum flow in the given network.

#### Input

The first line contains two integers **n** and **m** (**1** ≤ **n** ≤ **100**, **1** ≤ **m** ≤ **10000**) - respectively the number of vertices and edges in the network. Each of the following **m** lines contains three numbers `u`

, _{i}`v`

and _{i}`c`

(_{i}**1** ≤ `u`

, _{i}`v`

≤ _{i}**n**, **1** ≤ `c`

≤ _{i}**10000**), meaning that between vertices `u`

and _{i}`v`

in the network there is an edge with capacity _{i}`c`

. Vertex _{i}**1** is the source, and the vertex **n** is the destination. Graph of the network is undirected and can contain multiple edges. All numbers are integers.

#### Output

Print the maximum flow in the given network.

Input example #1

3 3 1 2 3 1 3 5 3 2 7

Output example #1

8