#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m;
bitset<N> dp[2][100][N];
bool vis[N][3];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    dp[w][0][u][v] = true;
  }
  for (int i = 1; i <= 60; i++) {
    for (int u = 1; u <= n; u++)
      for (int mid = 1; mid <= n; mid++)
        for (int k = 0; k <= 1; k++)
          if (dp[k][i - 1][u][mid]) dp[k][i][u] |= dp[k ^ 1][i - 1][mid];
  }
  long long ans = 0;
  vector<int> s(0);
  for (int i = 1; i <= n; i++) s.push_back(i);
  int cur = 0;
  for (int i = 60; i >= 0; i--) {
    set<int> news;
    for (int u : s)
      for (int v = 1; v <= n; v++)
        if (dp[cur][i][u][v]) news.insert(v);
    if (news.size()) {
      ans += 1LL << i;
      s.clear();
      for (int u : news) s.push_back(u);
      cur ^= 1;
    }
  }
  if (ans > (long long)1e18)
    cout << -1;
  else
    cout << ans;
  return 0;
}
