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[i] and c[i] (1 ≤ u[i], v[i] ≤ n, 1 ≤ c[i] ≤ 10000), meaning that between vertices u[i] and v[i] in the network there is an edge with capacity c[i]. Vertex 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.

Examples