#include <bits/stdc++.h>
using namespace std;
const int N = 500;
int n, m;
bitset<N> dp[N][2][61];
map<pair<int, int>, int> res;
long long fr(int v, int cur) {
  if (res.find(make_pair(v, cur)) != res.end()) return res[make_pair(v, cur)];
  int mx = 60;
  while (mx >= 0 && dp[v][cur][mx].count() == 0) mx--;
  if (mx == -1) return 0;
  long long ans = 1LL << mx;
  long long pl = 0;
  for (int i = 0; i < n; i++)
    if (dp[v][cur][mx][i]) {
      long long c = fr(i, 1 - cur);
      if (c == -1) {
        res.insert(make_pair(make_pair(v, cur), -1));
        return -1;
      }
      pl = max(pl, c);
    }
  ans += pl;
  if (ans > 1e18) ans = -1;
  res.insert(make_pair(make_pair(v, cur), ans));
  return ans;
}
int main() {
  srand(time(NULL));
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    x--;
    y--;
    dp[x][z][0][y] = 1;
  }
  for (int j = 1; j < 61; j++) {
    for (int k = 0; k < 2; k++) {
      bitset<N> s[N];
      for (int i = 0; i < n; i++) {
        for (int v = 0; v < n; v++)
          if (dp[v][1 - k][j - 1][i]) s[i][v] = 1;
      }
      for (int v = 0; v < n; v++) {
        for (int i = 0; i < n; i++) {
          bitset<N> t = dp[v][k][j - 1] & s[i];
          if (t.count() > 0) dp[v][k][j][i] = 1;
        }
      }
    }
  }
  if (dp[0][0][60].count() > 0)
    cout << "-1\n";
  else
    cout << fr(0, 0) << endl;
  return 0;
}
