#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int inf = 1e9;
struct ev{
int t, id, others;
}e[N];
int st[N], en[N];
int v2[N];
map <int, int> f;
void add(int l, int r, int x){
for(int i = l;i <= r;i++){
v2[i]+=x;
}
}
void solve(){
int n, m;
int ans;
cin>>n>>m;
ans = m;
f.clear();
for(int i = 0;i < n;i++){
st[i] = m + 1;
en[i] = -1;
}
for(int i = 0;i < m;i++){
v2[i] = 0;
}
for(int i = 0;i < m;i++){
cin>>e[i].t>>e[i].id>>e[i].others;
e[i].t--;
if(f.find(e[i].t) != f.end() && f[e[i].t] != e[i].others + 1){
ans = min(ans, i);
//cout<<"i1\n";
}
f[e[i].t] = e[i].others + 1;
e[i].id--;
/// apply update
if(st[e[i].id] != m + 1){
add(st[e[i].id], en[e[i].id], -1);
}
st[e[i].id] = min(st[e[i].id], e[i].t);
en[e[i].id] = max(en[e[i].id], e[i].t);
add(st[e[i].id], en[e[i].id], 1);
int mnppl = 0, prv = 0;
for(auto j : f){
if(j.second < v2[j.first]){
ans = min(ans, i);
//cout<<"i2\n";
}
mnppl+=max(0, j.second - prv);
prv = j.second;
}
if(mnppl > n){
ans = min(ans, i);
//cout<<"i3\n";
}
}
cout<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}
/**
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
**/
