#include <bits/stdc++.h>
using namespace std;
const int N = 505, L = 65;
long long INF = 1e18;
struct MX {
  long long n, m;
  bitset<N> str[N], stn[N];
  MX(int ni = N - 4, int mi = N - 4) {
    n = ni;
    m = mi;
    clear();
  }
  void clear() {
    for (int i = 0; i < N - 2; i++) {
      for (int j = 0; j < N - 2; j++) {
        str[i][j] = 0;
        stn[j][i] = 0;
      }
    }
    return;
  }
  MX zarb(MX &tmp) {
    MX ans = MX(n, tmp.m);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < tmp.m; j++) {
        bitset<N> tmpl;
        tmpl = str[i] & tmp.stn[j];
        if (tmpl.count()) {
          ans.str[i][j] = 1;
          ans.stn[j][i] = 1;
        }
      }
    }
    return (ans);
  }
  MX power(long long tmp) {
    MX ans = MX(n, m);
    for (int i = 0; i < n; i++) {
      ans.str[i][i] = 1;
      ans.stn[i][i] = 1;
    }
    MX a = MX(n, m);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        a.str[i][j] = str[i][j];
        a.stn[j][i] = stn[j][i];
      }
    }
    long long cur = tmp;
    while (cur) {
      if (cur % 2) ans = ans.zarb(a);
      a = a.zarb(a);
      cur /= 2;
    }
    return (ans);
  }
};
MX A[L], B[L];
int n, m;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  A[0] = MX(n + 1, n + 1);
  B[0] = MX(n + 1, n + 1);
  for (int i = 0, u, v, t; i < m; i++) {
    cin >> u >> v >> t;
    if (!t)
      A[0].str[u][v] = 1, A[0].stn[v][u] = 1;
    else
      B[0].str[u][v] = 1, B[0].stn[v][u] = 1;
  }
  for (int i = 1; i <= 62; i++) {
    A[i] = MX(n + 1, n + 1);
    B[i] = MX(n + 1, n + 1);
    A[i] = A[i - 1].zarb(B[i - 1]);
    B[i] = B[i - 1].zarb(A[i - 1]);
  }
  int cur = 0;
  MX tmp = MX(2, n + 1);
  tmp.str[1][1] = 1, tmp.stn[1][1] = 1;
  while (cur < 63) {
    tmp = tmp.zarb(A[cur]);
    if (!tmp.str[1].count()) break;
    tmp.clear();
    tmp.str[1][1] = 1, tmp.stn[1][1] = 1;
    cur++;
  }
  cur--;
  if (cur < 0) return cout << 0 << '\n', 0;
  long long ans = (1ll << cur);
  tmp.clear();
  tmp.str[1][1] = 1, tmp.stn[1][1] = 1;
  MX C = tmp.zarb(A[cur]);
  cur--;
  bool flag = false;
  while (cur >= 0) {
    if (ans >= INF) return cout << -1 << '\n', 0;
    if (flag)
      tmp = C.zarb(A[cur]);
    else
      tmp = C.zarb(B[cur]);
    if (tmp.str[1].count()) {
      C = tmp;
      ans += (1ll << cur);
      flag = !flag;
    }
    cur--;
  }
  if (ans >= INF) return cout << -1 << '\n', 0;
  cout << ans << '\n';
  return 0;
}
