Given a graph with $N\ (2 ≤ N ≤ 5,000)$ vertices numbered $1$ to $N$ and $M\ (1 ≤ M ≤ 30,000)$ undirected, weighted edges, compute the maximum flow / minimum cut from vertex $1$ to vertex $N$.

The first line contains the two integers $N,M$. 

The next $M$ lines each contain three integers $A, B, C$, denoting that there is an edge of capacity $C\ (1 ≤ C ≤ 10^9)$ between nodes $A$ and $B\ (1 ≤ A, B ≤ N)$. 

Note that it is possible for there to be duplicate edges, as well as an edge from a node to itself.

Print a single integer (which may not fit into a 32-bit integer) denoting the maximum flow / minimum cut between $1$ and $N$.

5

Viewing the problem as max-flow, we may send 3 units of flow through the path 1 - 2 - 3 - 4 and 2 units of flow through the path 1 - 3 - 4. Viewing the problem as min-cut, we may cut the first and third edges. Either way the total is 5.