123パズル

[problemUrl]: https://atcoder.jp/contests/kupc2019/tasks/kupc2019_h あなたはペンシルパズルを作っています。 このパズルは $ 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 $ となることがわかります。 不満度の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ l_1 $ $ u_2 $ $ v_2 $ $ l_2 $ $ : $ $ u_M $ $ v_M $ $ l_M $

不満度の最小値を出力せよ。

4 3
1 2 0
2 3 1
3 4 0

0

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

1

### 制約 - $ 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\} $ - 入力はすべて整数である。 ### Sample Explanation 1 $ A\ =\ (1,\ 2,\ 2,\ 3) $ とすればよいです。 このとき、 - $ A_1\ <\ A_2 $ - $ A_2\ \leq\ A_3 $ - $ A_3\ <\ A_4 $ のすべてを満たし、不満度は $ 0 $ です。 ### Sample Explanation 2 $ A\ =\ (1,\ 2,\ 2,\ 2,\ 3,\ 2) $ とすれば、$ C\ =\ (0,\ 0,\ 1,\ 0,\ 0,\ 0,\ 0,\ 0,\ 0) $ となり、不満度を $ 1 $ にすることができます。 不満度を $ 0 $ にすることはできないので、不満度の最小値は $ 1 $ です。