最大流

フローネットワークは始点 $s$ と終点 $t$ が区別された有向グラフです。フローネットワークの各辺 $(u, v)$ には容量 $c(u, v)$ が設定されており、この容量を超えないフローが流れます。始点 $s$ から終点 $t$ への最大流を求めてください。

入力

フローネットワーク $G(V,E)$ が以下の形式で与えられる。

$|V|\;|E|$
$u_0\;v_0\;c_0$
$u_1\;v_1\;c_1$
:
$u_{|E|-1}\;v_{|E|-1}\;c_{|E|-1}$

$|V|$, $|E|$ はそれぞれフローネットワーク $G$ の頂点の数と辺の数を示す。 $G$ の頂点にはそれぞれ $0, 1, ..., |V|-1$ の番号が付けられており、始点を 0、終点を $|V|-1$ とする。

$u_i$, $v_i$, $c_i$ はフローネットワーク $G$ の $i$ 番目の辺であり、頂点 $u_i$ から頂点 $v_i$ に向かって容量が $c_i$ の辺があることを表す。

出力

最大流を１行に出力する。

制約

• $2 \leq |V| \leq 100$
• $1 \leq |E| \leq 1000$
• $0 \leq c_i \leq 10000$

入力例

4 5
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2

出力例

3

---