#include <bits/stdc++.h>
using namespace std;
template <class _Tp>
void ckmax(_Tp &a, _Tp b) {
  if (a < b) a = b;
}
template <class _Tp>
void ckmin(_Tp &a, _Tp b) {
  if (a > b) a = b;
}
template <class _Tp>
_Tp gcd(_Tp a, _Tp b) {
  return (b == 0) ? (a) : (gcd(b, a % b));
}
int read() {
  char ch = getchar();
  bool f = 1;
  int x = 0;
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') f = 0, ch = getchar();
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch & 15);
    ch = getchar();
  }
  return f ? x : -x;
}
const int inf = 1000000000;
const long long Inf = 1000000000000000000ll;
int n, m;
struct mat {
  int r, c;
  bitset<550> a[550 + 5];
  bitset<550> &operator[](int x) { return a[x]; }
  void init(int r_, int c_) {
    r = r_, c = c_;
    for (int i = 1; i <= r; ++i) a[i].reset();
  }
  mat friend operator*(mat a, mat b) {
    mat c;
    c.init(a.r, b.c);
    for (int i = 1; i <= a.r; ++i)
      for (int k = 1; k <= a.c; ++k)
        if (a[i][k]) c[i] |= b[k];
    return c;
  }
} f[61 + 5][2], a, b;
int main() {
  n = read();
  m = read();
  f[0][0].init(n, n);
  f[0][1].init(n, n);
  for (int i = 1; i <= m; ++i) {
    int x = read(), y = read(), z = read();
    f[0][z][x][y] = 1;
  }
  for (int i = 1; i <= 61; ++i) {
    f[i][0] = f[i - 1][0] * f[i - 1][1];
    f[i][1] = f[i - 1][1] * f[i - 1][0];
  }
  long long ans = 0;
  int opt = 0;
  a.init(1, n);
  a[1][1] = 1;
  for (int k = 61; k >= 0; --k) {
    b = a * f[k][opt];
    if (b[1].count()) {
      a = b;
      opt ^= 1;
      ans += (1ll << k);
    }
    if (ans > 1e18) {
      puts("-1");
      return 0;
    }
  }
  printf("%lld\n", ans);
  return 0;
}
