#include <bits/stdc++.h>
using namespace std;
const int MAX_N = (int)2e5 + 123;
int n, m;
bitset<505> to[2][505], nx[2][63][505], now, nw;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v, tp; i <= m; i++) {
    scanf("%d%d%d", &u, &v, &tp);
    to[tp][u][v] = v;
  }
  for (int it = 0; it < 63; it++) {
    for (int v = 1; v <= n; v++) {
      if (it == 0) {
        nx[0][0][v] = to[0][v];
        nx[1][0][v] = to[1][v];
        continue;
      }
      for (int to = 1; to <= n; to++) {
        if (nx[0][it - 1][v][to]) nx[0][it][v] |= nx[1][it - 1][to];
        if (nx[1][it - 1][v][to]) nx[1][it][v] |= nx[0][it - 1][to];
      }
    }
  }
  int tp = 0;
  now[1] = 1;
  long long ans = 0;
  while (1) {
    if (ans > (long long)1e18) {
      puts("-1");
      return 0;
    }
    int good = 0;
    for (int it = 62; it >= 0; it--) {
      bool found = 0;
      for (int i = 1; i <= n; i++)
        if (now[i] && nx[tp][it][i].count() > 0) {
          found = 1;
          break;
        }
      if (!found) continue;
      good = 1;
      ans += (1LL << it);
      nw.reset();
      for (int i = 1; i <= n; i++)
        if (now[i]) nw |= nx[tp][it][i];
      swap(now, nw);
      tp ^= 1;
      break;
    }
    if (!good) break;
  }
  if (ans > (long long)1e18)
    puts("-1");
  else
    cout << ans << endl;
  return 0;
}
