#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+5;
int const mod=1e9+7;
int fx[N];
int fst[N];
int lst[N];
int sn[N];
int ed[N];
vector<vector<int>> sta;
int n,m;
void solve(){
cin>>n>>m;
for (int i = 0; i < m; ++i)
{
int t,p,c;
cin>>t>>p>>c;
sta.push_back({t,p,c});
}
int low=0,high=m+1;
while(high-low>1){
int mid=(high+low)/2;
for (int i = 0; i <=n; ++i){
fst[i]=m+1;
lst[i]=0;
}
for(int i=0;i<=m;i++){
fx[i]=0;
ed[i]=0;
sn[i]=-1;
}
vector<vector<int>> tsta;
bool ans=1;
for (int i = 0; i < mid; ++i){
int p=sta[i][1];
int t=sta[i][0];
int c=sta[i][2];
if(sn[t]==-1)
sn[t]=c;
else if(sn[t]!=c)
ans=0;
sn[t]=c;
fst[p]=min(fst[p],t);
lst[p]=max(lst[p],t);
tsta.push_back(sta[i]);
ed[lst[p]+1]++;
}
for (int i = 1; i <=n; ++i)
if(lst[i]>0){
fx[fst[i]]++;
fx[lst[i]+1]--;
}
for (int i = 1; i <=m; ++i){
fx[i]+=fx[i-1];
ed[i]+=ed[i-1];
}
sort(tsta.begin(), tsta.end());
int curt=m;
int ex=0;
for(int i=mid-1;i>=0;i--){
int t=tsta[i][0],c=tsta[i][2]+1;
while(curt>t){
int edh=ed[t+1]-ed[t];
ex-=edh;
ex=max(0,ex);
curt--;
}
int edh=ed[t+1]-ed[t];
ex-=edh;
ex=max(0,ex);
fx[t]+=ex;
if(fx[t]>c || fx[t]+(ed[t]-ex)<c){
ans=0;
break;
}
ex+=(ed[t]-ex)-(c-fx[t]);
curt--;
}
if(ans)
low=mid;
else
high=mid;
}
cout<<low<<endl;
}
int main(){
int t=1;
cin>>t;
while(t--)
solve();
return 0;
}
