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