#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>

#define frs first
#define scn second
#define mkp make_pair
#define phb push_back
#define ppb pop_back

using namespace std;

typedef pair< int, int > Pr;
typedef pair< int, Pr > Cmd;

int N, M;
Cmd C[10010];

vector< int > graph[110], stk;
int dfi, dfn[110], lwn[110], cmp[110];
int vst[110], vst_cnt;
bool is_in_stk[110];

bitset< 110 > dscn[110], ancs[110];
bool is_zero[110], is_nonzero[110];
bitset< 110 > is_intr[110];

void read();
void soups_on();
bool yee_haw(int);
void tarjan(int);
void dfs(int, int);

int main() {
  while (cin >> N >> M, N + M)
    read(), soups_on();

  return 0;
}

void read() {
  int s, u, v;

  for (int i = 0; i < M; ++i)
    cin >> s >> u >> v, C[i] = mkp(s, mkp(u, v));
}

void soups_on() {
  int low, up, mid;

  low = 0, up = M;
  while (low < up) {
    mid = (low + up) / 2 + 1;
    if (yee_haw(mid))
      low = mid;
    else
      up = mid - 1;
  }

  cout << low << "\n";
}

bool yee_haw(int lm) {
  int u, v;
  vector< Pr > t[6];

  for (int i = 0; i < lm; ++i)
    t[C[i].frs].phb(C[i].scn);

  for (int i = 1; i <= N; ++i)
    graph[i].clear();

  // build graph
  for (int i = 0; i < int(t[1].size()); ++i) {
    u = t[1][i].frs, v = t[1][i].scn;
    graph[v].phb(u);
  }

  for (int i = 0; i < int(t[2].size()); ++i) {
    u = t[2][i].frs, v = t[2][i].scn;
    graph[u].phb(v), graph[v].phb(u);
  }

  // find scc
  ++vst_cnt, dfi = 0;
  for (int i = 1; i <= N; ++i)
    if (vst[i] != vst_cnt)
      tarjan(i);

  for (int i = 1; i <= N; ++i)
    dscn[i].reset(), ancs[i].reset(), dscn[i].set(i), ancs[i].set(i);

  // find descendants and ancestors
  for (int i = 1; i <= N; ++i)
    if (cmp[i] == i)
      ++vst_cnt, dfs(i, i);

  fill(&is_zero[0], &is_zero[N + 1], false);
  fill(&is_nonzero[0], &is_nonzero[N + 1], false);

  for (int i = 1; i <= N; ++i)
    is_intr[i].reset();

  // dealing with constraint type 5

  for (int i = 0; i < int(t[5].size()); ++i) {
    u = cmp[t[5][i].frs], v = cmp[t[5][i].scn];
    bitset< 110 > tmp = ancs[u] | ancs[v];
    for (int j = 1; j <= N; ++j)
      if (ancs[u][j] || ancs[v][j])
        is_nonzero[j] = true, is_intr[j] |= tmp;
  }

  // dealing with constraint type 4
  for (int i = 0; i < int(t[4].size()); ++i) {
    u = cmp[t[4][i].frs], v = cmp[t[4][i].scn];
    if (u == v)
      is_zero[u] = true;
    else {
      if (is_intr[u][v])
        return false;
      bitset< 110 > tmp = dscn[u] & dscn[v];
      for (int j = 1; j <= N; ++j)
        if (tmp[j])
          is_zero[j] = true;
    }
  }

  // dealing with constraint type 3
  for (int i = 0; i < int(t[3].size()); ++i) {
    u = cmp[t[3][i].frs], v = cmp[t[3][i].scn];
    if (u == v) return false;
    if (is_zero[u] && is_zero[v]) return false;
  }

  // dealing with other confliction between constraint type 4 and 5
  for (int i = 1; i <= N; ++i)
    if (cmp[i] == i && (is_zero[i] && is_nonzero[i]))
      return false;

  return true;
}

void tarjan(int u) {
  int v;

  vst[u] = vst_cnt;
  dfn[u] = lwn[u] = ++dfi;
  stk.phb(u), is_in_stk[u] = true;

  for (int i = 0; i < int(graph[u].size()); ++i)
    if (vst[v = graph[u][i]] != vst_cnt)
      tarjan(v), lwn[u] = min(lwn[u], lwn[v]);
    else if (is_in_stk[v])
      lwn[u] = min(lwn[u], dfn[v]);

  if (dfn[u] == lwn[u]) {
    do {
      v = stk.back(), stk.ppb(), is_in_stk[v] = false;
      cmp[v] = u;
    } while (u != v);
  }
}

void dfs(int u, int k) {
  int v;

  vst[u] = vst_cnt;
  for (int i = 0; i < int(graph[u].size()); ++i)
    if (vst[v = graph[u][i]] != vst_cnt) {
      if (cmp[v] == v)
        dscn[k].set(v), ancs[v].set(k);
      dfs(v, k);
    }
}

Measured memory_bytes: 1648