银河灿星

题目描述

银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。

现在有$n$颗我们所关注的恒星，恒星的编号为$1$,$2$,$\ldots$,$n$，我们用一个正整数来表示恒星的亮度，恒星的亮度最低为$1$。

现在给出$m$对恒星之间的相对关系，每个相对关系的详细信息如下：

• $1$ $A$ $B$：说明恒星$A$与恒星$B$的亮度相等。
• $2$ $A$ $B$：说明恒星$A$的亮度小于恒星$B$的亮度。
• $3$ $A$ $B$：说明恒星$A$的亮度不小于恒星$B$的亮度。
• $4$ $A$ $B$：说明恒星$A$的亮度大于恒星$B$的亮度。
• $5$ $A$ $B$：说明恒星$A$的亮度不大于恒星$B$的亮度。

请你确认我们所关注的$n$颗恒星的亮度值总和至少有多大。

输入格式

第一行输入两个整数$n$，$m$，分别表示关心恒星的总数与确定恒星关系数。

接下来$m$行，每行三个正整数$T$，$A$，$B$，表示一对恒星之间的相对关系。

输出格式

输出一个整数表示答案，无解则输出$-1$。

数据范围与提示

对于$100\%$的数据，$1 \leq n \leq 10^{5}$，$0 \leq m \leq 10^{5}$。

本题采用子任务捆绑测试。对于每个子任务，你只有通过了这个子任务的所有数据，才能获得这个子任务的分数。

• 子任务$1$（$30$分）：$n \leq 100$；
• 子任务$2$（$70$分）：无特殊限制。

样例

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

11

见galaxy2.in

见galaxy2.out