P10935 Galaxy

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.

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 an integer representing the result. If there is no solution, output $-1$.

Constraints: $1\le N \le 100000$，$1\le M \le 100000$. Translated by ChatGPT 5