#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z, pre, cur;
struct Graph {
  bool a[505][505][2];
  void clean() { memset(a, 0, sizeof(a)); }
} G[2];
long long ans, lim[505][2];
void check(int j) {
  if (lim[j][0] > 1e18) {
    puts("-1");
    exit(0);
  }
  lim[j][1] = min(lim[j][1], (long long)1000000000000000001);
}
bitset<505> B1[505], B2[505], B3[505], B4[505];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &x, &y, &z);
    if (!z)
      lim[x][0] = 1;
    else
      lim[x][1] = 1;
    G[0].a[x][y][z] = true;
  }
  for (long long i = 1;; i <<= 1) {
    pre = cur, cur ^= 1;
    G[cur].clean();
    bool flag = false;
    for (int j = 1; j <= n; ++j)
      B1[j].reset(), B2[j].reset(), B3[j].reset(), B4[j].reset();
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        if (G[pre].a[j][k][0]) B1[j].set(k), B2[k].set(j);
        if (G[pre].a[j][k][1]) B3[j].set(k), B4[k].set(j);
      }
    }
    for (int j = 1; j <= n; ++j)
      for (int k = 1; k <= n; ++k) {
        if ((B1[j] & B4[k]).count())
          flag = true, G[cur].a[j][k][0] = true, lim[j][0] = (i << 1);
        if ((B3[j] & B2[k]).count())
          G[cur].a[j][k][1] = true, lim[j][1] = (i << 1);
        check(j);
      }
    for (int j = 1; j <= n; ++j)
      for (int k = 1; k <= n; ++k) {
        if (G[cur].a[j][k][0])
          lim[j][0] = max(lim[j][0], (i << 1) + min((i << 1), lim[k][1]));
        if (G[cur].a[j][k][1])
          lim[j][1] = max(lim[j][1], (i << 1) + min((i << 1), lim[k][0]));
        check(j);
      }
    if (!flag) break;
    if (i > 1e18) {
      puts("-1");
      return 0;
    }
  }
  for (int i = 1; i <= n; ++i) ans = max(ans, lim[i][0]);
  if (ans > 1e18) {
    puts("-1");
    return 0;
  }
  printf("%lld\n", ans);
  return 0;
}
