Competitions

# Maximum flow and matchings

# Maximum Flow A

The undirected graph without loops and multiple edges with **n** vertices is given (the vertices are numbered from **1** to **n**). For each edge we know its capacity. Find the value of the maximum flow from the vertex **1** to the vertex **n**. The current can flow along each edge in both directions.

#### Input

Two numbers **n** and **k** (**2** ≤ **n** ≤ **100**, **0** ≤ **k** ≤ **n** * (**n** - **1**) / **2**) - the number of vertices and edges in a graph. Each of the next **k** lines contains three numbers **a**, **b**, **c** (**1** ≤ **a**, **b** ≤ **n**, **1** ≤ **c** ≤ `10`

) - the vertices, connected with an edge, and the capacity of this edge.^{9}

#### Output

Print the maximum flow from the vertex **1** to vertex **n**.

Input example #1

5 7 1 2 2 2 5 5 1 3 6 3 4 2 4 5 1 3 2 3 2 4 1

Output example #1

6