問題文

あなたはペンシルパズルを作っています。

このパズルは N 個の頂点と M 本の有向辺からなる単純グラフの形をしています。

頂点には 1 から N までの番号が、辺には 1 から M までの番号がついています。

辺 i は、頂点 u_i から頂点 v_i へ向かう辺であり、ラベル l_i (l_i \in \{0,1\}) がついています。

このパズルの遊び方は以下の通りです。

• 各頂点に数 1,2,3 のうちの 1 つを書き込む。頂点 i に書かれた数を A_i とする。
• すべての i (1 \leq i \leq M) について以下を満たす書き込み方が、パズルの解である。
  • l_i = 0 のとき、A_{u_i} < A_{v_i}
  • l_i = 1 のとき、A_{u_i} \leq A_{v_i}

あなたは上のようなパズルを思いつきましたが、解の存在についてはまだ確認していません。

解が存在しない場合でもできるだけ満足する答えを探したいので、あなたは以下で定義される不満度が最小となるような書き込み方を求めようとしています。

• すべての i (1 \leq i \leq M) について、次のようにして C_i を求める。
  • l_i = 0 のとき、C_i = \max(0,A_{u_i}-A_{v_i}+1)
  • l_i = 1 のとき、C_i = \max(0,A_{u_i}-A_{v_i})
• 不満度は、 C_i の総和である。

パズルの解が存在するとき、不満度の最小値は 0 となることがわかります。

不満度の最小値を求めてください。

制約

• 2 \leq N \leq 5000
• 1 \leq M \leq \min(5000, N \times (N-1))
• 1 \leq u_i,v_i \leq N
• u_i \neq v_i
• すべての 1 \leq i,j \leq N について、i \neq j ならば (u_i, v_i) \neq (u_j, v_j)
• l_i \in \{0,1\}
• 入力はすべて整数である。

入力例 1

4 3
1 2 0
2 3 1
3 4 0

出力例 1

0

A = (1, 2, 2, 3) とすればよいです。

このとき、

• A_1 < A_2
• A_2 \leq A_3
• A_3 < A_4

のすべてを満たし、不満度は 0 です。

入力例 2

6 9
1 2 1
2 3 1
3 4 0
4 5 0
1 6 0
6 2 1
6 3 1
4 6 1
6 5 0

出力例 2

1

A = (1, 2, 2, 2, 3, 2) とすれば、C = (0, 0, 1, 0, 0, 0, 0, 0, 0) となり、不満度を 1 にすることができます。 不満度を 0 にすることはできないので、不満度の最小値は 1 です。