Maximum flow — Eolymp

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100, $1 \leq m \leq 10000$ 1 \leq m \leq 10000) — the number of vertices and edges in the network, respectively. Each of the following $m$ lines contains three integers $u_{i}$ u_i, $v_{i}$ v_i, and $c_{i}$ c_i ( $1 \leq u_{i}, v_{i} \leq n$ 1 \leq u_i, v_i \leq n, $1 \leq c_{i} \leq 10000$ 1 \leq c_i \leq 10000), indicating that there is an edge with capacity $c_{i}$ c_i between vertices $u_{i}$ u_i and $v_{i}$ v_i. Vertex $1$ is the source and vertex $n$ is the sink. The network graph is undirected and may contain multiple edges. All input numbers are integers.

Output

Print the maximum flow in the given network.

Examples

Example 1

Loading