时间限制：1秒　　内存限制：256M

---

题目描述

幼儿园里有 \(N\) 个小朋友，\(\text{lxhgww}\) 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，\(\text{lxhgww}\) 需要满足小朋友们的 \(K\) 个要求。幼儿园的糖果总是有限的，\(\text{lxhgww}\) 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入格式

输入的第一行是两个整数 \(N,K\)。接下来 \(K\) 行，每行 \(3\) 个数字 \(X,A,B\)，表示小朋友们的要求。

• 如果 \(X=1\)， 表示第 \(A\) 个小朋友分到的糖果必须和第 \(B\) 个小朋友分到的糖果一样多；
• 如果 \(X=2\)， 表示第 \(A\) 个小朋友分到的糖果必须少于第 \(B\) 个小朋友分到的糖果；
• 如果 \(X=3\)， 表示第 \(A\) 个小朋友分到的糖果必须不少于第 \(B\) 个小朋友分到的糖果；
• 如果 \(X=4\)， 表示第 \(A\) 个小朋友分到的糖果必须多于第 \(B\) 个小朋友分到的糖果；
• 如果 \(X=5\)， 表示第 \(A\) 个小朋友分到的糖果必须不多于第 \(B\) 个小朋友分到的糖果；

输出格式

输出一行一个整数，表示 \(\text{lxhgww}\) 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，则输出 \(-1\)。

输入输出样例 #1

输入 #1

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

输出 #1

11

说明/提示

对于 \(30\%\) 的数据，\(N\leq100\)；

对于 \(100\%\) 的数据，\(1\leq N,K\leq10^5, 1\leq X\leq5, 1\leq A, B\leq N\)。

---