Pangの研究対象の一つに最大流問題があります。

$n$ 頂点を持つ有向グラフ $G$ が以下の条件を満たすとき、これを universe グラフと呼びます。

• $G$ は、頂点 1 から頂点 $n$ への、長さが等しい $k$ 本の頂点素な単純パスの和集合である。

パスの集合が頂点素であるとは、それらが内部頂点を共有しないことを指します。 パスにおいて、端点ではない頂点を内部頂点と呼びます。 パスが単純であるとは、その頂点がすべて異なることを指します。

$n$ 頂点 $m$ 辺を持つ universe グラフ $G$ が与えられます。各辺には非負整数の容量が割り当てられています。 頂点 1 から頂点 $n$ への最大流を可能な限り大きくするために、以下の操作を任意の回数（0回を含む）行うことができます。

• 正の容量を持つ辺 $e$ を選び、その容量を 1 減らし、別の辺の容量を 1 増やす。

これを達成するために必要な最小の操作回数を求めてください。

入力

1 行目に 2 つの整数 $n$ と $m$ ($2 \le n \le 100000, 1 \le m \le 200000$) が与えられます。 続く $m$ 行の各行には、3 つの整数 $x, y, z$ が与えられ、頂点 $x$ から頂点 $y$ へ向かう容量 $z$ の辺を表します ($1 \le x, y \le n, 0 \le z \le 1000000000$)。

入力されるグラフは、多重辺や自己ループを持たない universe グラフであることが保証されています。

出力

最小の操作回数を 1 つの整数で出力してください。

入出力例

入力 1

4 3
1 2 1
2 3 2
3 4 3

出力 1

1

入力 2

4 4
1 2 1
1 3 1
2 4 2
3 4 2

出力 2

1