附加文件

【题目描述】

小明同学正在参加区间速算比赛。

N 个互不相同的整数排成一行，依次编号为 1 ~ N。小明需要快速回答主持人的 M 个问题，每个问题形如：a b，即快速计算出区间 [a, b] 之间的所有数的最小值。

只有全部回答正确，才算 AC，否则即 WA。

现在我们并不知道 N 个整数是什么，但我们已经知道了小明对于 M 个问题的答案，请你推断小明有没有可能 AC 或者一定 WA。如果小明同学有可能 AC，你需要输出一个整数 0。否则，你需要输出小明第一次回答一定错误是在第几个问题。

【输入格式】

• 第一行：两个正整数 $N$ 和 $M$
• 接下来的 $M$ 行：每行三个整数 $a, b, c$，表示小明对于 [a, b] 之间的所有数的最小值回答是 c。

【输出格式】

一个整数，表示答案。

【样例1输入】

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

【样例1输出】

3

【样例2输入】

5 4
1 5 6
2 5 7
3 5 8
4 4 9

【样例2输出】

0

【数据范围】

100% 的数据：$1 ≤ N ≤ 10^6$, $1 ≤ M ≤ 3×10^4$, $1 ≤ a ≤ b ≤ N$, $1 ≤ c ≤ 10^9$