#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n,m;
cin>>n>>m;
vector<vector<int>> st;
for (int i=0;i<m;i++)
{
int t,p,j;
cin>>t>>p>>j;
st.push_back({t,p-1,j});
}
int s=0,e=m+1;
while (s+1<e)
{
int mid=(s+e)/2;
bool pos=1;
int mn[n],mx[n]={},vl[m+2]={},a[m+1];
for (int i=0;i<mid;i++)
{
a[st[i][0]]=st[i][2];
if (!mn[st[i][1]]) mn[st[i][1]]=st[i][0];
mn[st[i][1]]=min(mn[st[i][1]],st[i][0]);
mx[st[i][1]]=max(mx[st[i][1]],st[i][0]);
}
for (int i=0;i<n;i++)
vl[mn[i]]++,vl[mx[i]+1]--;
for (int i=2;i<=m;i++)
vl[i]+=vl[i-1];
vector<pair<int,int>> v;
for (int i=0;i<mid;i++)
{
if (vl[st[i][0]]-1>st[i][2] or a[st[i][0]]!=st[i][2])
pos=0;
v.push_back({st[i][0],st[i][2]+1});
}
sort(v.begin(),v.end());
int lef=n,pre=0;
for (auto [t,i]:v)
{
if (i>pre)
lef-=i-pre;
pre=i;
}
if (lef<0) pos=0;
if (pos)
s=mid;
else
e=mid;
}
cout<<s<<endl;
}
signed main()
{
int t;
cin>>t;
while (t--)
solve();
return 0;
}
