#include <bits/stdc++.h>
using namespace std;
const int N = 505, M = 500005;
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  bool p = 0;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') p = 1;
  for (; c >= '0' && c <= '9'; c = getchar())
    x = (x << 3) + (x << 1) + (c ^ 48);
  if (p) x = -x;
}
int n, m;
bitset<N> f[65][2][N], Hina, Aya;
int main() {
  read(n);
  read(m);
  for (int i = 1, x, y, w; i <= m; ++i) {
    read(x);
    read(y);
    read(w);
    f[0][w][x][y] = 1;
  }
  for (int i = 1; i <= 64; ++i) {
    for (int w = 0; w < 2; ++w) {
      for (int x = 1; x <= n; ++x) {
        for (int k = 1; k <= n; ++k) {
          if (f[i - 1][w][x][k]) f[i][w][x] |= f[i - 1][1 - w][k];
        }
      }
    }
  }
  if (f[64][0][1].count()) {
    printf("-1\n");
    return 0;
  }
  unsigned long long ans = 0;
  Aya[1] = 1;
  int typ = 0;
  for (int i = 63; i >= 0; --i) {
    Hina.reset();
    for (int j = 1; j <= n; ++j) {
      if (Aya[j]) Hina |= f[i][typ][j];
    }
    if (Hina.count()) {
      ans += (1ull << i);
      Aya = Hina;
      typ = 1 - typ;
    }
  }
  if (ans > 1000000000000000000) {
    printf("-1\n");
  } else {
    printf("%I64d\n", ans);
  }
  return 0;
}
