#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MAXD = 60;
struct Matrix {
  int n, m;
  bitset<MAXN> a[MAXN], b[MAXN];
  Matrix() {}
  Matrix(int r, int c) : n(r), m(c) {}
  void set(int x, int y, bool k) { a[x][y] = b[y][x] = k; }
  Matrix operator*(const Matrix& b) const {
    Matrix c(n, b.m);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= b.m; j++)
        c.a[i][j] = c.b[j][i] = (a[i] & b.b[j]).any();
    return c;
  }
} P[MAXD], B[MAXD];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  P[0] = B[0] = Matrix(n, n);
  for (int i = 1; i <= m; i++) {
    int u, v, t;
    scanf("%d%d%d", &u, &v, &t);
    if (t == 0)
      P[0].set(u, v, 1);
    else
      B[0].set(u, v, 1);
  }
  for (int i = 1; i < 60; i++)
    P[i] = P[i - 1] * B[i - 1], B[i] = B[i - 1] * P[i - 1];
  Matrix cur(1, n);
  cur.set(1, 1, 1);
  long long ans = 0;
  for (int i = 59, t = 0; i >= 0; i--) {
    Matrix tmp = cur * (t == 0 ? P[i] : B[i]);
    bool flag = 0;
    for (int i = 1; i <= n; i++)
      if (tmp.a[1][i]) {
        flag = 1;
        break;
      }
    if (flag) cur = tmp, ans += 1ll << i, t ^= 1;
  }
  printf("%lld\n", ans > 1E18 ? -1 : ans);
  return 0;
}
