Description

一天公司有 $n$ 个员工和 $m$ 个员工记录，每个员工只会在连续的一段时间内工作。现在给出 $m$ 条记录，表示某个时刻某个人在工作以及除他之外还有多少人在工作。求最大的 $k$ 使得前 $k$ 条记录互不矛盾。

Input Format

第一行一个整数 $T(1 \le T \le 50)$，表示一个测试点有 $T$ 组测试数据。

接下来的每组测试数据的第一行包含两个由空格分隔的整数 $n,m(1 \le n, m \le 10^5)$，分别表示员工数量和员工记录数量。接下来的 $m$ 行中，每一行包含三个由空格分隔的整数 $t,j,i(1 \le t \le m，1 \le j \le n,0 \le i \le n )$。表示在时间为 $t$ 时，编号为 $j$ 的员工在办公室里工作并且除了他以外还有 $i$ 个员工在那里。

Output Format

输出共 $T$ 行。对于每一个测试数据，输出最大的 $k$ 使得前 $k$ 条记录互不矛盾。两个答案之间用换行隔开。

2
3 5
1 1 1
1 2 1
2 3 1
4 1 1
4 2 1
3 3
3 3 0
2 2 0
1 1 0

4
3