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 ui, vi and ci (1 ≤ ui, vi ≤ n, 1 ≤ ci ≤ 10000), meaning that between vertices ui and vi in the network there is an edge with capacity ci. 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.