测试数据来自 system/1671

背景

做题目前，讲一个寓言。

有一对兄弟，他们的家住在80层楼上。有一天他们外出旅行回家，发现大楼停电了！虽然他们背着大包的行李，但看来没有什么别的选择，于是哥哥对弟弟说，我们就爬楼梯上去！于是，他们背着两大包行李开始爬楼梯。爬到20楼的时候他们开始累了，哥哥说“包包太重了，不如这样吧，我们把包包放在这里，等来电后坐电梯来拿。”于是，他们把行李放在了20楼，轻松多了，继续向上爬。

他们有说有笑地往上爬，但是好景不长，到了40楼，两人实在累了。想到还只爬了一半，两人开始互相埋怨，指责对方不注意大楼的停电公告，才会落得如此下常他们边吵边爬，就这样一路爬到了60楼。到了60楼，他们累得连吵架的力气也没有了。弟弟对哥哥说，“我们不要吵了，爬完它吧。”于是他们默默地继续爬楼，终于80楼到了！兴奋地来到家门口兄弟俩才发现他们的钥匙留在了20楼的包包里了。

下面开始做题。

描述

给出M个三元组(a,b,c)，表示a~b中最小值为c.
找出最小的I满足：存在N长序列满足1~I-1中所有的三元组的要求，并且不存在N长序列满足1~I中所有的三元组的要求，若存在N长序列满足所有三元组要求，输出0。

格式

输入格式

第一行两个整数n,m
接下来m行，每行一个三元组(a,b,c);
保证1<=n<=10^6 0<=m<=50000 a<=b a+500>=b 0<=c<=n

输出格式

一个数，如题

样例1

样例输入1

20 4
1 10 7
5 19 7
3 12 8
11 15 12

样例输出1

3

限制

各个测试点1s

提示

From usaco 2008.