#include <bits/stdc++.h>
using namespace std;
const long long maxn = 512, logn = 70, inf = 1e18 + 1;
long long n;
vector<bitset<maxn> > operator*(vector<bitset<maxn> > a,
                                vector<bitset<maxn> > b) {
  vector<bitset<maxn> > ans(n);
  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++) ans[i][j] = 0;
  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++)
      if (a[i][j]) ans[i] |= b[j];
  return ans;
}
bool good(vector<bitset<maxn> > a) {
  bool ans = 0;
  for (long long i = 0; i < n; i++)
    if (a[i].count() > 0) ans = 1;
  return ans;
}
vector<bitset<maxn> > a[logn], b[logn];
long long solve(long long l, bool r, vector<bitset<maxn> > m) {
  if (l < 0) return 0;
  if (!r) {
    if (good(m * a[l]))
      return (1ll << l) + solve(l - 1, !r, m * a[l]);
    else
      return solve(l - 1, r, m);
  } else {
    if (good(m * b[l]))
      return (1ll << l) + solve(l - 1, !r, m * b[l]);
    else
      return solve(l - 1, r, m);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  clock_t start = clock();
  long long m;
  cin >> n >> m;
  bitset<maxn> p;
  a[0].assign(n, p), b[0].assign(n, p);
  while (m--) {
    long long u, v, type;
    cin >> u >> v >> type;
    u--, v--;
    if (type == 0)
      a[0][u][v] = 1;
    else
      b[0][u][v] = 1;
  }
  for (long long l = 1; l < logn; l++) {
    a[l] = a[l - 1] * b[l - 1];
    b[l] = b[l - 1] * a[l - 1];
  }
  vector<bitset<maxn> > z(n);
  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++) z[i][j] = 0;
  for (long long i = 0; i < n; i++) z[i][i] = 1;
  long long ans = solve(60, 0, z);
  if (ans >= inf)
    cout << -1;
  else
    cout << ans;
  return 0;
}
