#include <stdio.h>
#include <string.h>
#define N 100000
#define M 100000
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int solve(int *tt, int *ii, int *cc, int n, int m, int k) {
static int ll[N], rr[N], hh[M], dd0[M + 1], dd1[M + 1];
int m_, h, i, t, c, d, d0, d1;
memset(dd0, 0, m * sizeof *dd0);
for (i = 0; i < n; i++)
ll[i] = m, rr[i] = -1;
for (h = 0; h < k; h++) {
i = ii[h], t = tt[h];
ll[i] = min(ll[i], t), rr[i] = max(rr[i], t);
if (dd0[t] == 0)
dd0[t] = cc[h];
else if (dd0[t] != cc[h])
return 0;
}
m_ = 0;
for (t = 0; t < m; t++)
if (dd0[t] != 0)
dd0[hh[t] = m_++] = dd0[t];
dd0[m_] = 0;
for (h = m_; h > 0; h--)
dd0[h] -= dd0[h - 1];
memset(dd1, 0, (m_ + 1) * sizeof *dd1);
c = 0;
for (i = 0; i < n; i++)
if (ll[i] <= rr[i])
dd1[hh[ll[i]]]--, dd1[hh[rr[i]] + 1]++;
else
c++;
d0 = d1 = 0;
for (h = 0; h < m_; h++) {
if (dd0[h] > 0)
d0 += dd0[h];
if (dd1[h] > 0)
d1 += dd1[h];
if (dd0[h] < 0) {
d = -dd0[h];
if (d <= d1)
d1 -= d;
else {
d -= d1, d1 = 0;
if (d > d0 || d > c)
return 0;
d0 -= d, c -= d;
}
}
if (dd1[h] < 0) {
d = -dd1[h];
if (d <= d0)
d0 -= d;
else {
d -= d0, d0 = 0;
if (d > d1)
return 0;
d1 -= d;
}
}
}
return 1;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
static int tt[M], ii[M], cc[M];
int n, m, k, h, lower, upper;
scanf("%d%d", &n, &m);
for (h = 0; h < m; h++)
scanf("%d%d%d", &tt[h], &ii[h], &cc[h]), tt[h]--, ii[h]--, cc[h]++;
lower = 0, upper = m + 1;
while (upper - lower > 1) {
k = (lower + upper) / 2;
if (solve(tt, ii, cc, n, m, k))
lower = k;
else
upper = k;
}
printf("%d\n", lower);
}
return 0;
}
