题目描述

天文学家正在观测一片星域中的 $N$ 颗恒星。每颗恒星的亮度用一个正整数表示，数值越大越亮，最暗为 $1$。目前已知 $M$ 对恒星之间的亮度关系。你的任务是为每颗恒星分配一个亮度值，满足所有已知关系，并使所有恒星的亮度总和尽可能小。

输入格式

第一行两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行三个整数 $T, A, B$，表示恒星 $A$ 和 $B$ 的亮度关系：

• $T=1$：$A$ 和 $B$ 亮度相等
• $T=2$：$A$ 的亮度严格小于 $B$
• $T=3$：$A$ 的亮度大于等于 $B$
• $T=4$：$A$ 的亮度严格大于 $B$
• $T=5$：$A$ 的亮度小于等于 $B$

输出格式

输出一个整数，表示亮度总和的最小值。若不存在合法方案，输出 $-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

提示

$1 \le N \le 10^5$，$1 \le M \le 10^5$。