#include<stdio.h>
#include<string.h>
#define MAXN 405
#define MAXM 160010
struct Node
{
    int from,to,next;
}edge1[MAXM],edge2[MAXM];
struct Node1
{
    int a,b,c;
}s[MAXM];
int n,m,head1[MAXN],head2[MAXN],visit1[MAXN],visit2[MAXN],tol1,tol2;
int Tcnt,Bcnt,Belong[MAXN],T[MAXN];
void add(int a,int b)
{
    edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++;
    edge2[tol2].from=b;edge2[tol2].to=a;edge2[tol2].next=head2[b];head2[b]=tol2++;
}    
void dfs1(int i)
{
    int j,u;
    visit1[i]=1;
    for(j=head1[i];j!=-1;j=edge1[j].next)
    {
        u=edge1[j].to;
        if(!visit1[u])  dfs1(u);
    }    
    T[Tcnt++]=i;
}  
void dfs2(int i)
{
    int j,u;
    visit2[i]=1;
    Belong[i]=Bcnt;
    for(j=head2[i];j!=-1;j=edge2[j].next)
    {
        u=edge2[j].to;
        if(!visit2[u])  dfs2(u);
    }    
} 
int main()
{
    int i,ans,right,left,mid,ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
           scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
        left=0;
        right=m;
        while(left<=right)
        {
            mid=(left+right)/2;
            for(i=0;i<2*n;i++)
            {
                head1[i]=-1;
                head2[i]=-1;
                visit1[i]=0;
                visit2[i]=0;
            }  
            tol1=tol2=0;
            Tcnt=Bcnt=0;
            for(i=0;i<mid;i++)
            {
                if(s[i].c==0)
                {
                    add(s[i].a,s[i].b+n);
                    add(s[i].b,s[i].a+n);
                }    
                else if(s[i].c==1)
                {
                    add(s[i].a,s[i].b);
                    add(s[i].b,s[i].a);
                    add(s[i].a+n,s[i].b+n);
                    add(s[i].b+n,s[i].a+n);
                }    
                else if(s[i].c==2)
                {
                    add(s[i].a+n,s[i].b);
                    add(s[i].b+n,s[i].a);
                }    
            }
            for(i=0;i<2*n;i++)
               if(!visit1[i])  dfs1(i);      
            for(i=Tcnt-1;i>=0;i--)
            {
                if(!visit2[T[i]])
                {
                    dfs2(T[i]);
                    Bcnt++;
                }    
            }    
            for(i=0;i<n;i++)
            {
                if(Belong[i]==Belong[i+n]) break;
            }    
            if(i==n)
            {
                ans=mid;left=mid+1;
            }    
            else  right=mid-1;
        }    
        printf("%d\n",ans);
    }    
    return 0;
}