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\le n\le 100,0\le k\le n\cdot (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\le a,b\le n,1\le c\le 10^9)$ — the vertices, connected with an edge, and the capacity of this edge.

Output

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

Examples