#include <bits/stdc++.h>
using namespace std;
const long long LG = 61, INF = 1000 * 1000 * 1000, LEN = INF * INF, N = 501;
bool g[LG][2][N][N];
long long n, m;
bool can[N], can1[N];
long long solve() {
  for (long long i = 1; i <= n; ++i) can[i] = 1;
  bool w = 0;
  long long ans = 0;
  for (long long p = LG - 1; p >= 0; --p) {
    bool first = 0;
    for (long long i = 1; i <= n; ++i)
      for (long long j = 1; j <= n; ++j) first |= can[i] && g[p][w][i][j];
    if (first) {
      ans += 1ll << p;
      memset(can1, 0, sizeof can1);
      for (long long i = 1; i <= n; ++i)
        for (long long j = 1; j <= n; ++j)
          if (can[i] && g[p][w][i][j]) can1[j] = 1;
      for (long long i = 1; i <= n; ++i) can[i] = can1[i];
      w ^= 1;
    }
  }
  return ans;
}
bitset<N> l[2][N], r[2][N];
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (long long i = 0; i < m; ++i) {
    long long u, v, t;
    cin >> u >> v >> t;
    g[0][t][u][v] = 1;
  }
  for (long long p = 1; p < LG; ++p) {
    for (long long t = 0; t < 2; ++t)
      for (long long i = 1; i <= n; ++i)
        for (long long j = 1; j <= n; ++j) l[t][i][j] = g[p - 1][t][i][j];
    for (long long t = 0; t < 2; ++t)
      for (long long i = 1; i <= n; ++i)
        for (long long j = 1; j <= n; ++j) r[t][i][j] = g[p - 1][t][j][i];
    for (long long i = 1; i <= n; ++i)
      for (long long j = 1; j <= n; ++j) {
        g[p][0][i][j] = (l[0][i] & r[1][j]).any();
        g[p][1][i][j] = (l[1][i] & r[0][j]).any();
      }
  }
  long long ans = solve();
  if (ans > LEN)
    cout << "-1\n";
  else
    cout << ans << '\n';
}
