1 #include<stdio.h>
  2 #include<memory.h>
  3 #define N 205
  4 #define M 10005
  5 #define E 60005
  6 int head[N * 2], id[N*2],pre[N*2],low[N*2],s[N*2],nxt[E],ev[E],a[M],b[M],c[M];
  7 int stop, cnt, scnt, n, m, num;
  8 void readin()
  9 {
 10     int i;
 11     scanf("%d%d", &n, &m);
 12     for (i = 0; i < m; i++)
 13         scanf("%d%d%d", &a[i], &b[i], &c[i]);
 14 }
 15 void tarjan(int v, int n)
 16 {
 17     int pv, t, minc = low[v] = pre[v] = cnt++;
 18     s[stop++] = v;
 19     for (pv = head[v]; pv != -1; pv = nxt[pv])
 20     {
 21         if (-1 == pre[ev[pv]])
 22             tarjan(ev[pv], n);
 23         if (low[ev[pv]] < minc)
 24             minc = low[ev[pv]];
 25     }
 26     if (minc < low[v])
 27     {
 28         low[v] = minc;
 29         return;
 30     }
 31     do
 32     {
 33         id[t = s[--stop]] = scnt;
 34         low[t] = n;
 35     } while (t != v);
 36     ++scnt;
 37 }
 38 void addedge(int u, int v)
 39 {
 40     nxt[++num] = head[u];
 41     head[u] = num;
 42     ev[num] = v;
 43 }
 44 void solve()
 45 {
 46     int l, r, mid, ans, i;
 47     bool flag;
 48     l = 0;
 49     r = m;
 50     ans = 0;
 51     while (l <= r)
 52     {
 53         mid = (l + r) >> 1;
 54         memset(head, -1, sizeof(head));
 55         num = -1;
 56         for (i = 0; i < mid; i++)
 57         {
 58             switch (c[i])
 59             {
 60             case 0:
 61                 addedge(2 * a[i], 2 * b[i] + 1);
 62                 addedge(2 * b[i], 2 * a[i] + 1);
 63                 break;
 64             case 1:
 65                 addedge(2 * a[i], 2 * b[i]);
 66                 addedge(2 * a[i] + 1, 2 * b[i] + 1);
 67                 addedge(2 * b[i], 2 * a[i]);
 68                 addedge(2 * b[i] + 1, 2 * a[i] + 1);
 69                 break;
 70             case 2:
 71                 addedge(2 * a[i] + 1, 2 * b[i]);
 72                 addedge(2 * b[i] + 1, 2 * a[i]);
 73                 break;
 74             }
 75         }
 76         stop = cnt = scnt = 0;
 77         memset(pre, -1, sizeof(pre));
 78         for (i = 0; i < n * 2; i++)
 79             if (pre[i] == -1)
 80                 tarjan(i, n * 2);
 81         flag = true;
 82         for (i = 0; i < n; i++)
 83             if (id[i * 2] == id[i * 2 + 1])
 84             {
 85                 flag = false;
 86                 break;
 87             }
 88         if (flag)
 89         {
 90             ans = mid;
 91             l = mid + 1;
 92         }
 93         else
 94             r = mid - 1;
 95     }
 96     printf("%d\n", ans);
 97 }
 98 int main()
 99 {
100     int cas;
101     scanf("%d", &cas);
102     while (cas--)
103     {
104         readin();
105         solve();
106     }
107     return 0;
108 }