#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
int n, m;
long long ans;
bitset<510> f[65][2][510], use, now;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, aa, bb, cc; i <= m; i++) {
    scanf("%d%d%d", &aa, &bb, &cc);
    f[0][cc][aa][bb] = 1;
  }
  for (int s = 1; s <= 60; s++)
    for (int p = 0; p <= 1; p++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          if (f[s - 1][p][i][j]) f[s][p][i] |= f[s - 1][p ^ 1][j];
  for (int i = 1; i <= n; i++)
    if (f[60][0][1][i]) {
      puts("-1");
      return 0;
    }
  use[1] = 1;
  for (int k = 59, t = 0; k >= 0; k--) {
    now = 0;
    for (int i = 1; i <= n; i++)
      if (use[i]) now |= f[k][t][i];
    if (now.any()) {
      use = now;
      t ^= 1;
      ans += (1LL << k);
      if (ans > inf) {
        puts("-1");
        return 0;
      }
    }
  }
  if (ans > inf) {
    puts("-1");
    return 0;
  } else
    printf("%lld\n", ans);
  return 0;
}
