1 # include<stdio.h>
  2 # include<string.h>
  3 # define M 80005
  4 # define N 500
  5 struct node{
  6     int from,to,next;
  7 }edge1[M],edge2[M];
  8 struct node1{
  9     int a,b,c;
 10 }s[M];
 11 int n,m,head1[N],head2[N],visit1[N],visit2[N],tol1,tol2,Tcnt,Bcnt,T[N],Belong[N];
 12 void add(int a,int b)
 13 {
 14     edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++;
 15     edge2[tol2].from=b;edge2[tol2].to=a;edge2[tol2].next=head2[b];head2[b]=tol2++;
 16 }
 17 void dfs1(int i)
 18 {
 19     int j,u;
 20     visit1[i]=1;
 21     for(j=head1[i];j!=-1;j=edge1[j].next)
 22     {
 23         u=edge1[j].to;
 24         if(!visit1[u]) dfs1(u);
 25     }
 26     T[Tcnt++]=i;
 27 }
 28 void dfs2(int i)
 29 {
 30     int j,u;
 31     visit2[i]=1;
 32     Belong[i]=Bcnt;
 33     for(j=head2[i];j!=-1;j=edge2[j].next)
 34     {
 35         u=edge2[j].to;
 36         if(!visit2[u]) dfs2(u);
 37     }
 38 }
 39 int main()
 40 {
 41     int i,ans,right,left,mid,ncase;
 42     scanf("%d",&ncase);
 43     while(ncase--)
 44     {
 45         scanf("%d%d",&n,&m);
 46         for(i=0;i<m;i++)
 47             scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
 48         left=0;
 49         right=m;
 50         while(left<=right)
 51         {
 52             mid=(left+right)/2;
 53             memset(head1,-1,sizeof(head1));
 54             memset(head2,-1,sizeof(head2));
 55             memset(visit1,0,sizeof(visit1));
 56             memset(visit2,0,sizeof(visit2));
 57             tol1=tol2=0;
 58             Tcnt=Bcnt=0;
 59             for(i=0;i<mid;i++)
 60             {
 61                 if(s[i].c==0)
 62                 {
 63                     add(s[i].a,s[i].b+n);
 64                     add(s[i].b,s[i].a+n);
 65                 }
 66                 else if(s[i].c==1)
 67                 {
 68                     add(s[i].a,s[i].b);
 69                     add(s[i].b,s[i].a);
 70                     add(s[i].a+n,s[i].b+n);
 71                     add(s[i].b+n,s[i].a+n);
 72                 }
 73                 else if(s[i].c==2)
 74                 {
 75                     add(s[i].a+n,s[i].b);
 76                     add(s[i].b+n,s[i].a);
 77                   /*add(s[i].a,s[i].b+n);
 78                     add(s[i].b,s[i].a+n);*///这样写就wa了
 79                 }
 80             }
 81             for(i=0;i<2*n;i++)
 82                 if(!visit1[i]) dfs1(i);
 83                 for(i=Tcnt-1;i>=0;i--)
 84                 {
 85                     if(!visit2[T[i]])
 86                     {
 87                         dfs2(T[i]);
 88                         Bcnt++;
 89                     }
 90                 }
 91                 for(i=0;i<n;i++)
 92                 {
 93                     if(Belong[i]==Belong[i+n]) break;
 94                 }
 95                 if(i==n) {ans=mid;left=mid+1;}
 96                 else right=mid-1;
 97         }
 98         printf("%d\n",ans);
 99     }
100     return 0;
101 }