#include <bits/stdc++.h>
using namespace std;
template <class T>
bool umin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <class T>
bool umax(T &x, T y) {
  return y > x ? x = y, 1 : 0;
}
const int N = 505;
int n, m, g[N][N][2];
bitset<N> dp[100][2][N], ok, tmp;
signed main() {
  cin >> n >> m;
  for (int i = 1, u, v, w; i <= m; ++i) {
    cin >> u >> v >> w;
    dp[0][w][u][v] = 1;
  }
  for (int i = 1; i <= 60; ++i) {
    for (int u = 1; u <= n; ++u) {
      for (int k = 1; k <= n; ++k) {
        if (dp[i - 1][0][u][k]) dp[i][0][u] |= dp[i - 1][1][k];
        if (dp[i - 1][1][u][k]) dp[i][1][u] |= dp[i - 1][0][k];
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    if (dp[60][0][i].count()) {
      puts("-1");
      return 0;
    }
  long long ans = 0;
  ok[1] = 1;
  int cur = 0;
  for (int i = 59; i >= 0; --i) {
    tmp = 0;
    for (int u = 1; u <= n; ++u)
      if (ok[u]) tmp |= dp[i][cur][u];
    if (tmp.count()) {
      for (int u = 1; u <= n; ++u) ok[u] = tmp[u];
      ans |= (1ll << i);
      if (ans > 1e18) {
        ans = -1;
        break;
      }
      cur ^= 1;
    }
  }
  cout << ans << "\n";
  return 0;
}
