#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
const long long MAXST = 61;
const long long INF = 1e18;
int n, m;
bitset<MAXN> g_p[MAXN];
bitset<MAXN> g_v[MAXN];
bool used_dp[MAXN][MAXST][2];
bitset<MAXN> dp[MAXN][MAXST][2];
bitset<MAXN> pereh(bitset<MAXN> cur_sost, int st, int tp);
bitset<MAXN> rec(int v, int st, int tp) {
  if (used_dp[v][st][tp]) {
    return dp[v][st][tp];
  }
  used_dp[v][st][tp] = true;
  if (tp == 0) {
    if (st == 0) {
      dp[v][st][tp] = g_p[v];
      return dp[v][st][tp];
    }
    dp[v][st][tp] = pereh(rec(v, st - 1, tp), st - 1, 1);
    return dp[v][st][tp];
  } else {
    if (st == 0) {
      dp[v][st][tp] = g_v[v];
      return dp[v][st][tp];
    }
    dp[v][st][tp] = pereh(rec(v, st - 1, tp), st - 1, 0);
    return dp[v][st][tp];
  }
}
bitset<MAXN> pereh(bitset<MAXN> cur_sost, int st, int tp) {
  bitset<MAXN> ans;
  if (cur_sost.size() > 0) {
    for (int i = 0; i < MAXN; ++i) {
      if (cur_sost[i] == 1) ans = ans | rec(i, st, tp);
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int v, to, tp;
    cin >> v >> to >> tp;
    v--;
    to--;
    if (tp == 0) {
      g_p[v][to] = 1;
    } else {
      g_v[v][to] = 1;
    }
  }
  for (int i = 0; i < MAXN; ++i) {
    for (int j = 0; j < MAXST; ++j) {
      used_dp[i][j][0] = false;
      used_dp[i][j][1] = false;
    }
  }
  bitset<MAXN> cur_sost;
  cur_sost[0] = 1;
  int cur_ch = 0;
  long long ans_len = 0;
  for (int i = MAXST - 1; i >= 0; --i) {
    bitset<MAXN> next_per = pereh(cur_sost, i, cur_ch);
    if (next_per.count() > 0) {
      ans_len += (((long long)1) << ((long long)i));
      cur_sost = next_per;
      cur_ch ^= 1;
    }
  }
  bitset<MAXN> next_per = pereh(cur_sost, 0, cur_ch);
  if (next_per.count() > 0) {
    ans_len += (((long long)1) << ((long long)0));
    cur_sost = next_per;
  }
  if (ans_len > INF) {
    cout << -1 << endl;
  } else {
    cout << ans_len << endl;
  }
  return 0;
}
