#include <bits/stdc++.h>
using namespace std;
const int Maxn = 500;
const long long INF = 1e18;
int N, M;
bitset<Maxn + 3> f[63][2][Maxn + 3];
int main() {
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= M; i++) {
    int u, v, col;
    scanf("%d %d %d", &u, &v, &col);
    f[0][col][u][v] = 1;
  }
  for (int stp = 1; stp <= 60; stp++)
    for (int col = 0; col < 2; col++)
      for (int u = 1; u <= N; u++)
        for (int v = 1; v <= N; v++)
          if (f[stp - 1][col][u][v]) f[stp][col][u] |= f[stp - 1][col ^ 1][v];
  for (int i = 1; i <= N; i++)
    if (f[60][0][1][i]) {
      puts("-1");
      return 0;
    }
  long long ans = 0;
  bitset<Maxn + 3> g = 0;
  g[1] = 1;
  for (int stp = 59, col = 0; stp >= 0; stp--) {
    bitset<Maxn + 3> tmp = 0;
    for (int i = 1; i <= N; i++)
      if (g[i]) tmp |= f[stp][col][i];
    if (tmp.count()) {
      g = tmp, ans += (1LL << stp), col ^= 1;
      if (ans > INF) {
        puts("-1");
        return 0;
      }
    }
  }
  if (ans > INF)
    puts("-1");
  else
    printf("%lld\n", ans);
  return 0;
}
