#include <bits/stdc++.h>
using namespace std;
const long long inf = numeric_limits<long long>::max() / 2 - 1;
const long long mod = 1000000007;
const long double eps = 1e-8;
const long long maxn = 512;
long long n, m;
bitset<512> is[70][2][maxn];
bool isall[maxn][maxn];
bool cur[2][maxn];
int run() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    is[0][c][a][b] = 1;
  }
  for (int i = 0; i < 69; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (is[i][0][j][k]) {
          is[i + 1][0][j] |= is[i][1][k];
        }
        if (is[i][1][j][k]) {
          is[i + 1][1][j] |= is[i][0][k];
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (is[63][0][i].any()) {
      cout << -1;
      return 0;
    }
  }
  long long cur = 63;
  bitset<512> bs;
  for (int i = 0; i < n; i++) bs[i] = 1;
  long long ans = 0;
  bool isinvert = false;
  while (cur != -1) {
    bitset<512> nx;
    for (int i = 0; i < n; i++) {
      if (bs[i]) {
        nx |= is[cur][isinvert][i];
      }
    }
    if (nx.any()) {
      bs = nx;
      ans += (1LL << cur);
      isinvert ^= 1;
    }
    cur--;
  }
  if (ans > 1000000000000000000) {
    cout << -1;
  } else
    cout << ans;
  return 0;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  run();
  return 0;
}
