#include <bits/stdc++.h>
#pragma GCC optimize(2)
const int maxn = 505;
template <typename T>
inline void swap(T &a, T &b) {
  T tmp = a;
  a = b;
  b = tmp;
}
int n, m;
std::bitset<maxn> alpha[65][maxn], beta[65][maxn];
std::bitset<maxn> f[maxn], g[maxn];
void update(std::bitset<maxn> Alpha[maxn], std::bitset<maxn> Beta[maxn],
            std::bitset<maxn> alpha[maxn], std::bitset<maxn> beta[maxn]) {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      alpha[i][j] = Alpha[j][i], beta[i][j] = Beta[j][i];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      f[i][j] = (Alpha[i] & beta[j]).any();
      g[i][j] = (Beta[i] & alpha[j]).any();
    }
  }
  for (int i = 1; i <= n; i++) alpha[i] = f[i], beta[i] = g[i];
}
std::bitset<maxn> Gamma[maxn];
bool Pepper(int T) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (Gamma[1][i] && alpha[T][i][j]) {
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= n; j++) g[i][j] = alpha[T][j][i];
        for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= n; j++) {
            f[i][j] = (Gamma[i] & g[j]).any();
          }
        }
        for (int i = 1; i <= n; i++) Gamma[i] = f[i];
        for (int k = 0; k < T; k++) swap(alpha[k], beta[k]);
        return true;
      }
    }
  }
  return false;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v, type;
    scanf("%d%d%d", &u, &v, &type);
    if (type == 0)
      alpha[0][u][v] = 1;
    else
      beta[0][u][v] = 1;
  }
  for (int i = 1; i <= 63; i++)
    update(alpha[i - 1], beta[i - 1], alpha[i], beta[i]);
  long long answer = 0;
  Gamma[1][1] = 1;
  for (int i = 63; i >= 0; i--) {
    if (Pepper(i)) answer += 1ll << i;
    if (answer > 1e18) return puts("-1"), 0;
  }
  printf("%lld\n", answer);
  return 0;
}
