#include <bits/stdc++.h>
using namespace std;
const int N = 5e2;
const long long INF = 1e18;
int n, m;
bitset<N + 5> vis, tmp, f[65][2][N + 5];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v, w; i <= m; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    f[0][w][u][v] = 1;
  }
  for (int i = 1; i <= 60; ++i) {
    for (int u = 1; u <= n; ++u) {
      for (int v = 1; v <= n; ++v) {
        if (f[i - 1][0][u][v]) f[i][0][u] |= f[i - 1][1][v];
        if (f[i - 1][1][u][v]) f[i][1][u] |= f[i - 1][0][v];
      }
    }
  }
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (f[60][0][1][i]) return puts("-1"), 0;
  }
  vis[1] = 1;
  for (int i = 59, cur = 0; i >= 0; --i) {
    tmp.reset();
    for (int j = 1; j <= n; ++j) {
      if (vis[j]) {
        tmp |= f[i][cur][j];
      }
    }
    if (tmp.count()) {
      vis = tmp;
      ans |= 1LL << i;
      cur ^= 1;
    }
  }
  printf("%lld\n", ans > INF ? -1LL : ans);
  return 0;
}
