Background

On Farmer John's farm, whenever it rains, a pool of water accumulates on Bessie's favorite clover field. This means the field gets flooded, and it takes a long time for the grass to grow again. Therefore, Farmer John built a drainage system to keep Bessie's field from being flooded (do not worry, the rainwater will flow into a nearby creek). As a top-notch technician, Farmer John has installed a controller at one end of every ditch so that he can control the flow entering each ditch.

Problem Description

FJ knows the amount of water that can flow through each ditch per minute, as well as the exact layout of the drainage system (a network with the pond as the source and the creek as the sink). Note that between two places there may be more than one ditch.

Given this information, compute the maximum flow from the pond to the creek. For each ditch provided, water can flow in only one direction, and cycles may exist.

Input Format

• The first line contains two space-separated integers $N$ ($0 \le N \le 200$) and $M$ ($2 \le M \le 200$). $N$ is the number of ditches that FJ has already dug, and $M$ is the number of junctions. Junction $1$ is the pond, and junction $M$ is the creek.
• The second line to line $N + 1$: each line contains three integers $S_i, E_i, C_i$. $S_i$ and $E_i$ ($1 \le S_i, E_i \le M$) specify the two endpoints of a ditch, and water flows from $S_i$ to $E_i$. $C_i$ ($0 \le C_i \le 10^7$) is the maximum capacity of that ditch.

Output Format

Output a single integer — the maximum drainage flow.

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

50

Hint

The problem statement is translated from NOCOW.

USACO Training Section 4.2.

Constraints

For $100\%$ of the testdata, $0 \le N, M \le 200$, $0 \le C_i \le 10^7$.

Translated by ChatGPT 5