#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long w = 0, f = 1;
  char c = ' ';
  while (c < '0' || c > '9') c = getchar(), f = c == '-' ? -1 : f;
  while (c >= '0' && c <= '9') w = w * 10 + c - 48, c = getchar();
  return w * f;
}
const long long inf = 1e18;
long long n, m, ans;
bitset<505> f[2][62][505], la, now;
signed main() {
  n = read(), m = read();
  for (long long i = 1; i <= m; i++) {
    long long x = read(), y = read(), z = read();
    f[z][0][x][y] = 1;
  }
  for (long long i = 1; i < 62; i++)
    for (long long j = 1; j <= n; j++)
      for (long long k = 1; k <= n; k++) {
        if (f[0][i - 1][j][k]) f[0][i][j] |= f[1][i - 1][k];
        if (f[1][i - 1][j][k]) f[1][i][j] |= f[0][i - 1][k];
      }
  la[1] = 1;
  for (long long i = 62 - 1, u = 0; i >= 0; i--) {
    now.reset();
    for (long long j = 1; j <= n; j++)
      if (la[j]) now |= f[u][i][j];
    if (now.any()) u ^= 1, la = now, ans |= 1ll << i;
  }
  printf("%lld\n", ans >= inf ? -1ll : ans);
  return 0;
}
