最小費用最大流

頂点に $1$ から $N$ までの番号が付いた有向ネットワークが与えられる。頂点 $1$ から頂点 $N$ への最大流量 $F$ と、その流量を送るための最小総費用 $C$ を求めよ。辺 $i$ に流量 $x$ を送る費用は $x \cdot cost_i$ である。多重辺、自己ループ、容量や費用が $0$ の辺を許す。

入力は次の形式で与えられる。

$N\ M$ $u_1\ v_1\ cap_1\ cost_1$

$F$ と $C$ を空白で区切って一行に出力せよ。

• $2 \leq N \leq 500$.
• $0 \leq M \leq 20\,000$.
• $1\le u_i,v_i\le$ ().