AT_kupc2019_h 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}\

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

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

### 制約 - $ 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\