Maximum Flow 2

You are given a directed graph (G). Each edge in the graph has a specified capacity. Your task is to determine the maximum flow from vertex (1) to vertex (n).

Input

The first line of the input contains two integers, (n) and (m), representing the number of vertices and edges in the graph, respectively ((2 $\le$ n $\le$ 500), (1 $\le$ m $\le$ 10000)). Each of the following (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 a single integer, the value of the maximum flow from vertex (1) to vertex (n).

Examples