Maximum Flow 2

Input

The first line contains two integers $n$ and $m$ (2 \leq n \leq 500, 1 \leq m \leq 10000) — the number of vertices and the number of edges in the graph. Each of the next $m$ lines describes an edge with three integers: the starting vertex, the ending vertex, and the capacity of the edge. The capacity of each edge does not exceed 10^9.

Output

Output the value of the maximum flow from vertex $1$ to vertex $n$.

Examples