Chief

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

土豪大学有着全世界知名的食堂。厨房里有 N 个厨师,编号从 1 到 N,每天
需要做 M 道菜,但是每道菜需要的数量可能不同。
和其他地方不一样,土豪大学食堂里面的每道菜并不是一个人完成的,具体来说,
第 i 道菜需要编号从 a i 到 b i 的厨师做。
为了表彰这些厨师,土豪大学的校长准备从这 N 个厨师中选出一个最重要的厨
师。一个厨师参与制作的菜越多,那么这个厨师就越重要。
例如,有 3 个厨师,3 道菜。第 1 道菜需要编号从 1 到 3 的厨师完成,第 2
道菜需要编号从 2 到 3 的厨师完成,第 3 道菜需要编号从 2 到 2 的厨师完
成。并且第 1 道菜需要做 3 次,并且第 2 和 3 道菜需要做 2 次。那么最重
要的厨师是 2 号厨师,因为他们分别参与制作的菜的数目为 3, 7, 5。2 号厨师
做的最多。
现在给你这些信息,你需要找出谁是最重要的厨师。如果有多个,那么编号最小
的那个是最重要厨师。

Input

 输入第一行是一个整数 T,表示有 T 组数据。
每组数据的第一行有两个整数 N 和 M (1 <= N, M <= 1000),表示土豪大学中厨
师的数量和菜的种类。
接下来 M 行,每行三个整数 a i , b i 和 c i (1 <= a i <= b i <= N, 1 <= c i <= 1000),表
示第 i 道菜需要编号从 a i 到 b i 的厨师做,并且需要做 c i 次。

Output

 对于每组数据,输出最重要的厨师的编号,如果有多个,输出编号最小的那个。

Sample Input

4
1 1
1 1 2
2 2
1 2 3
2 2 4
4 3
2 4 3
1 1 3
1 4 3
3 3
1 3 3
2 3 2
2 2 2

Sample Output

1
2
1
2

Hint

 

Source

Ningbo_2014_Contest