Maximum Water Flow

You are given a water distribution system with n nodes and m directed pipes. Each pipe is represented by three integers u, v and c, denoting that there is a pipe from node u to node v with capacity c.

Your task is to compute the maximum water flow from the main reservoir located at node 1 to the target household at node n.

This problem can be formulated as the classic maximum flow problem. The flow conservation and capacity constraints must be respected, and the maximum amount of water that can be delivered to node n should be determined.

The maximum flow \(f^*\) can be computed using the Edmonds-Karp algorithm which is an implementation of the Ford-Fulkerson method using BFS to find augmenting paths.

inputFormat

The first line contains two integers n (number of nodes) and m (number of pipes).

The following m lines each contain three integers u, v and c representing a pipe from node u to node v with capacity c.

outputFormat

Output a single integer representing the maximum water flow from node 1 to node n.

## sample

4 5
1 2 100
2 3 50
1 3 50
3 4 100
2 4 100

150

</p>