二分答案，没有出现过的时刻没有用，可以进行离散化。
首先如果某个时刻出现多个人数，那么肯定矛盾。
然后按时间依次考虑，维护：
$t$：剩余可选人数。
$s$：现在必定有的人数。
$cl$：往左延伸的人数。
$cr$：往右延伸的人数。
如果现在有人必须加入，那么优先踢掉$cl$的人。
如果当前人多了，那么优先让$cr$的人结束工作。
如果最后剩余可选人数非负，则可行。
时间复杂度$O((n+m)log m)$。
#include<cstdio>
const int N=100010,BUF=33333333;
int T,n,m,i,e[N][3],l,r,mid,ans,a[N],b[N],c[N],p[N],L[N],R[N];char Buf[BUF],*buf=Buf;
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
inline void umin(int&a,int b){if(a>b)a=b;}
inline void umax(int&a,int b){if(a<b)a=b;}
bool check(int mid){
int i,t,x,y,cnt=0,s=0,cl=0,cr=0;
for(i=1;i<=n;i++)L[i]=N,R[i]=0;
for(i=1;i<=m;i++)a[i]=0;
for(i=1;i<=mid;i++){
t=e[i][0],x=e[i][1],y=e[i][2];
if(a[t]&&a[t]!=y)return 0;
a[t]=y,umin(L[x],t),umax(R[x],t);
}
for(i=1;i<=m;i++)if(a[i])p[i]=++cnt,a[cnt]=a[i],b[cnt]=c[cnt]=0;
for(i=1;i<=n;i++)if(R[i])b[p[L[i]]]++,c[p[R[i]]]++;
for(t=n,i=1;i<=cnt;i++){
s+=b[i];
if(s>a[i])return 0;
while(b[i]--)if(cl>0)cl--;else t--;
while(s+cl+cr<a[i])cl++,t--;
while(s+cl+cr>a[i])if(cr>0)cr--;else cl--;
s-=c[i],cr+=c[i];
if(t<0)return 0;
}
return 1;
}
int main(){
for(fread(Buf,1,BUF,stdin),read(T);T--;printf("%d
",ans)){
read(n),read(m);
for(i=1;i<=m;i++)read(e[i][0]),read(e[i][1]),read(e[i][2]),e[i][2]++;
l=2,r=m,ans=1;
while(l<=r)if(check(mid=(l+r)>>1))l=(ans=mid)+1;else r=mid-1;
}
return 0;
}