Max Flow in Drainage Network

Farmer John has detailed information about each drainage channel including its capacity per minute and the precise layout of the drainage network. The network is represented as a directed graph where nodes represent junctions. The water starts from the pond (node 1) and drains out to the creek (node n). Note that there may be multiple drainage channels between the same pair of nodes, and water flows only in the given direction along each channel. In some cases, water may even circulate in cycles.

Your task is to compute the maximum flow from the pond to the creek. In mathematical terms, if we denote the flow through an edge from node u to node v with capacity c by f(u,v), you must maximize the total flow \(\sum f(1, v)\) subject to the capacity and conservation constraints. The capacity constraint for every edge is given by \(0 \le f(u,v) \le c(u,v)\) and the flow conservation constraint for every intermediate node u (except source and sink) is:

[ \sum_{v} f(v,u) = \sum_{v} f(u,v) ]

Compute and output the maximum possible flow.

inputFormat

The first line contains two integers n and m, representing the number of nodes and the number of drainage channels, respectively.

Each of the next m lines contains three integers u, v and c, indicating that there is a directed drainage channel from node u to node v with capacity c.

Nodes are numbered from 1 to n where node 1 is the pond (source) and node n is the creek (sink).

outputFormat

Output a single integer representing the maximum amount of water (per minute) that can flow from the pond to the creek.

sample

4 5
1 2 40
1 3 20
2 3 10
2 4 20
3 4 30

50