#include <bits/stdc++.h>
using namespace std;
long long op, n, m, i, j, k, x, y, w, flag, ans, v[1010], g[1010];
bitset<502> a[61][2][502], b[61][2][502], c;
int main() {
  scanf("%lld%lld", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%lld%lld%lld", &x, &y, &w);
    a[0][w][x][y] = 1;
    b[0][w][y][x] = 1;
  }
  for (i = 1; i <= 60; i++) {
    for (j = 1; j <= n; j++)
      for (k = 1; k <= n; k++) {
        c = a[i - 1][0][j] & b[i - 1][1][k];
        if (c.count()) {
          a[i][0][j][k] = 1;
          b[i][0][k][j] = 1;
        }
        c = a[i - 1][1][j] & b[i - 1][0][k];
        if (c.count()) {
          a[i][1][j][k] = 1;
          b[i][1][k][j] = 1;
        }
      }
  }
  for (i = 1; i <= n; i++) v[i] = 1;
  op = 0;
  for (i = 60; i >= 0; i--) {
    flag = 0;
    for (j = 1; j <= n; j++)
      if (v[j]) {
        for (k = 1; k <= n; k++)
          if (a[i][op][j][k]) {
            flag = 1;
            break;
          }
      }
    if (!flag) continue;
    ans += 1ll << i;
    for (j = 1; j <= n; j++) g[j] = 0;
    for (j = 1; j <= n; j++)
      if (v[j]) {
        for (k = 1; k <= n; k++)
          if (a[i][op][j][k]) g[k] = 1;
      }
    for (j = 1; j <= n; j++) v[j] = g[j];
    op ^= 1;
  }
  if (ans > 1e18)
    puts("-1");
  else
    printf("%lld", ans);
}
