Maximum flow 0

UFOs have arrived and left us with this task.

Input

The first line of the input file contains two integers: n and m (2 ≤ n ≤ 10, 1 ≤ m ≤ n·(n-1)). These represent the number of vertices and edges in a graph where you need to determine the flow. Following this, each line describes an edge in the graph with three integers: a, b, c (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ c ≤ 100). These numbers specify an edge from vertex a to vertex b with a capacity of c. It is assured that the graph does not contain multiple edges between any two vertices.

Output

On a single line of the output file, print one number: the maximum flow from vertex 1 to vertex n.

Examples