#include <bits/stdc++.h>
int f[61][500][16], g[61][500][16], N, M, bN, V[16], tV[16], ty;
long long O;
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1, u, v, w; i <= M; i++) {
    scanf("%d%d%d", &u, &v, &w);
    u--, v--;
    (w ? g : f)[0][u][v >> 5] |= 1 << (v & 31);
  }
  bN = (N + 31) >> 5;
  for (int i = 1; i <= 60; i++)
    for (int j = 0; j < N; j++)
      for (int k = 0; k < N; k++) {
        if (f[i - 1][j][k >> 5] >> (k & 31) & 1)
          for (int l = 0; l < bN; l++) f[i][j][l] |= g[i - 1][k][l];
        if (g[i - 1][j][k >> 5] >> (k & 31) & 1)
          for (int l = 0; l < bN; l++) g[i][j][l] |= f[i - 1][k][l];
      }
  V[0] = 1;
  for (int i = 60; ~i; i--) {
    for (int j = 0; j < bN; j++) tV[j] = 0;
    int(*Z)[16] = (ty ? g : f)[i];
    for (int j = 0; j < N; j++)
      if (V[j >> 5] >> (j & 31) & 1)
        for (int k = 0; k < bN; k++) tV[k] |= Z[j][k];
    bool yes = 0;
    for (int j = 0; j < bN; j++)
      if (tV[j]) yes = 1;
    if (yes) {
      O |= 1LL << i;
      ty ^= 1;
      std::swap(V, tV);
    }
  }
  printf("%lld\n", O > 1000000000000000000LL ? -1LL : O);
  return 0;
}
