题目描述

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

我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 1。


现在对于 𝑁 颗我们关注的恒星，有 𝑀 对亮度之间的相对关系已经判明。


你的任务就是求出这 𝑁 颗恒星的亮度值总和至少有多大。

输入格式

第一行给出两个整数 𝑁 和 𝑀。

之后 𝑀 行，每行三个整数 𝑇,𝐴,𝐵，表示一对恒星 (𝐴,𝐵) 之间的亮度关系。恒星的编号从 1 开始。


如果 𝑇=1，说明 𝐴 和 𝐵 亮度相等。

如果 𝑇=2，说明 𝐴 的亮度小于 𝐵 的亮度。 如果 𝑇=3，说明 𝐴 的亮度不小于 𝐵 的亮度。 如果 𝑇=4，说明 𝐴 的亮度大于 𝐵 的亮度。 如果 𝑇=5，说明 𝐴 的亮度不大于 𝐵 的亮度。

N≤100000,M≤100000

输出格式

输出一个整数表示结果。

若无解，则输出 −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