#include <bits/stdc++.h>
using namespace std;
struct EDGE {
  int to, next, w;
} e[2000010];
int head[501], top;
void add(int u, int v, int w) {
  e[top].to = v;
  e[top].w = w;
  e[top].next = head[u];
  head[u] = top++;
}
int n;
struct matrix {
  bitset<501> a[501];
  matrix operator*(const matrix &ob) const {
    matrix rv;
    int i, k;
    for (i = 1; i <= n; i++) {
      for (k = 1; k <= n; k++) {
        if (a[i][k]) rv.a[i] |= ob.a[k];
      }
    }
    return rv;
  }
};
matrix a[61][2];
int main() {
  memset(head, 255, sizeof(head));
  int m;
  scanf("%d%d", &n, &m);
  int i;
  int u, v, w;
  for (i = 0; i < m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);
  }
  int j;
  for (i = 1; i <= n; i++) {
    for (j = head[i]; ~j; j = e[j].next) {
      a[0][e[j].w].a[e[j].to][i] = 1;
    }
  }
  for (int ii = 1; ii <= 60; ii++) {
    a[ii][0] = a[ii - 1][1] * a[ii - 1][0];
    a[ii][1] = a[ii - 1][0] * a[ii - 1][1];
  }
  matrix b, c;
  memset(b.a, 0, sizeof(b.a));
  b.a[1][1] = 1;
  int dir = 0;
  long long ans = 0;
  for (int ii = 60; ii >= 0; ii--) {
    c = a[ii][dir] * b;
    bool flag = 0;
    for (i = 1; i <= n; i++) {
      if (c.a[i][1]) {
        flag = 1;
        b = c;
        break;
      }
    }
    if (flag) {
      ans += 1ll << ii;
      dir ^= 1;
    }
    if (ans > 1000000000000000000) {
      puts("-1");
      return 0;
    }
  }
  printf("%lld\n", ans);
  return 0;
}
