Algorithmen 2012

Given a graph with n (2 ≤ n ≤ 50) vertices numbered 1 to n and m (1 ≤ m ≤ 1000) directed, weighted edges, compute the maximum flow  from vertex 1 to vertex n.

Input

The first line contains the two integers n and m. The next m lines each contain three integers u, v, and c, denoting that there is an edge (u,v) of capacity c, where 1 ≤ c ≤ 1000 and 1 ≤ u, v ≤ n.

Output

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

Example

Input:
4 5
1 2 3
1 3 4
2 4 4
3 2 1
3 4 2

Output: 6