Problem Description

You are creating a pencil-and-paper puzzle.

This puzzle is shaped like a simple graph consisting of $ N $ vertices and $ M $ directed edges.

The vertices are numbered from $ 1 $ to $ N $, and the edges are numbered from $ 1 $ to $ M $.

Edge $ i $ is an edge from vertex $ u_i $ to vertex $ v_i $ with a label $l_i\ (l_i\ \in\ \{0,1\})$.

The rules of the puzzle are as follows:

• Write one of the numbers $ 1, 2, 3 $ on each vertex. Let $ A_i $ be the number written on vertex $ i $.
• For all $i\ (1\ \leq\ i\ \leq\ M)$, the following conditions must be satisfied for the puzzle to be solved:
• If $l_i\ =\ 0$, then $A_{u_i}\ <\ A_{v_i}$
• If $l_i\ =\ 1$, then $A_{u_i}\ \leq\ A_{v_i}$

You have come up with such a puzzle, but you have not yet confirmed the existence of a solution.

Even if a solution does not exist, you want to find the most satisfying answer possible, so you are trying to find a way to write the numbers such that the dissatisfaction level defined below is minimized.

• For all $i\ (1\ \leq\ i\ \leq\ M)$, calculate $ C_i $ as follows:
• If $l_i\ =\ 0$, then $C_i\ =\ \max(0,A_{u_i}-A_{v_i}+1)$
• If $l_i\ =\ 1$, then $C_i\ =\ \max(0,A_{u_i}-A_{v_i})$
• The dissatisfaction level is the sum of $ C_i $.

When a solution exists for the puzzle, it is known that the minimum dissatisfaction level is $ 0 $.

Find the minimum dissatisfaction level.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ u_1 $ $ v_1 $ $ l_1 $ $ u_2 $ $ v_2 $ $ l_2 $ $ : $ $ u_M $ $ v_M $ $ l_M $

Output Format

Output the minimum dissatisfaction level.

Sample Input and Output

Sample Input #1

4 3
1 2 0
2 3 1
3 4 0

Sample Output #1

0

Sample Input #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

Sample Output #2

1

Notes/Hints

Constraints

• $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$
• For all $1\ \leq\ i,j\ \leq\ N$, if $i\ \neq\ j$, then $(u_i,\ v_i)\ \neq\ (u_j,\ v_j)$
• $l_i\ \in\ \{0,1\}$
• All inputs are integers.

Sample Explanation 1

$A\ =\ (1,\ 2,\ 2,\ 3)$ is a good choice. In this case:
- $A_1\ <\ A_2$
- $A_2\ \leq\ A_3$
- $A_3\ <\ A_4$
All conditions are satisfied, and the dissatisfaction level is $ 0 $.

Sample Explanation 2

$A\ =\ (1,\ 2,\ 2,\ 2,\ 3,\ 2)$ results in $C\ =\ (0,\ 0,\ 1,\ 0,\ 0,\ 0,\ 0,\ 0,\ 0)$, which can achieve a dissatisfaction level of $ 1 $. It is not possible to achieve a dissatisfaction level of $ 0 $, so the minimum dissatisfaction level is $ 1 $.

见题面 Input 部分

见题面 Output 部分