#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 505;
const long long inf = 1e18;
inline long long read() {
  long long weight = 0, symbol = 1;
  char in = getchar();
  while (!isdigit(in)) {
    if (in == '-') symbol = -1;
    in = getchar();
  }
  while (isdigit(in)) {
    weight = weight * 10 + in - '0';
    in = getchar();
  }
  return symbol * weight;
}
long long n, m;
bitset<MAXN> g[65][2][MAXN];
long long f[65][MAXN][2];
long long ans;
signed main() {
  n = read(), m = read();
  for (long long i = 1; i <= m; i++) {
    long long u = read(), v = read(), type = read();
    g[0][type][u][v] = 1;
  }
  for (long long t = 0; t <= 59; t++) {
    for (long long i = 1; i <= n; i++) {
      for (long long j = 1; j <= n; j++) {
        if (g[t][0][i][j]) g[t + 1][0][i] |= g[t][1][j];
        if (g[t][1][i][j]) g[t + 1][1][i] |= g[t][0][j];
      }
    }
  }
  memset(f, 0x80, sizeof(f));
  f[61][1][0] = 0;
  for (long long t = 60; t >= 0; t--) {
    for (long long i = 1; i <= n; i++)
      f[t][i][0] = f[t + 1][i][0], f[t][i][1] = f[t + 1][i][1];
    for (long long i = 1; i <= n; i++) {
      for (long long j = 1; j <= n; j++) {
        if (g[t][0][i][j])
          f[t][j][1] = max(f[t][j][1], f[t + 1][i][0] + (1ll << t));
        if (g[t][1][i][j])
          f[t][j][0] = max(f[t][j][0], f[t + 1][i][1] + (1ll << t));
      }
    }
  }
  for (long long i = 1; i <= n; i++)
    ans = max(ans, max(f[0][i][0], f[0][i][1]));
  if (ans > inf)
    puts("-1");
  else
    printf("%lld\n", ans);
  return 0;
}
