配点 : 300 点
問題文
你正在制作铅笔谜题。
这个谜题的形式是 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\}
- 所有输入均为整数。
入力
输入是按以下格式从标准输入给出的。
N M u_1 v_1 l_1 u_2 v_2 l_2 : u_M v_M l_M
出力
输出不满度的最小值。
入力例 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 。