Problem Description

There are countless stars in the galaxy, but we only care about the brightest ones.

We use a positive integer to represent a star's brightness. The larger the value is, the brighter the star is. The minimum brightness is $1$.

Now, among the $N$ stars we care about, $M$ pairs of relative brightness relationships have been determined.

Your task is to find the minimum possible value of the sum of brightness values of these $N$ stars.

Input Format

The first line contains two integers $N$ and $M$.

Then follow $M$ lines. Each line contains three integers $T, A, B$, describing the brightness relationship between a pair of stars $(A, B)$. Star indices start from $1$.

If $T = 1$, it means the brightness of $A$ and $B$ are equal.
If $T = 2$, it means the brightness of $A$ is less than the brightness of $B$.
If $T = 3$, it means the brightness of $A$ is not less than the brightness of $B$.
If $T = 4$, it means the brightness of $A$ is greater than the brightness of $B$.
If $T = 5$, it means the brightness of $A$ is not greater than the brightness of $B$.

Output Format

Output an integer representing the result.

If there is no solution, output $-1$.

5 7 
1 1 2 
2 3 2 
4 4 1 
3 4 5 
5 4 5 
2 3 5 
4 5 1 

11

Hint

Constraints: $1\le N \le 100000$，$1\le M \le 100000$.

Translated by ChatGPT 5