#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
bitset<510> can[maxn][2][64];
int N, M;
long long ans, best[maxn][2];
inline long long dfs(int now, int last) {
  if (best[now][last ^ 1] != -1)
    return best[now][last ^ 1];
  else
    best[now][last ^ 1] = 0;
  for (int i = 59; i >= 0; --i)
    if (can[now][last ^ 1][i].any()) {
      for (int j = 1; j <= N; ++j)
        if (can[now][last ^ 1][i][j])
          best[now][last ^ 1] =
              max(dfs(j, last ^ 1) + (1LL << i), best[now][last ^ 1]);
      break;
    }
  return best[now][last ^ 1];
}
int main() {
  scanf("%d %d", &N, &M);
  while (M--) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    can[a][c][0][b] = 1;
  }
  for (int i = 1; i <= 62; ++i)
    for (int j = 1; j <= N; ++j)
      for (int k = 0; k < 2; ++k)
        for (int l = 1; l <= N; ++l) {
          if (!can[j][k][i - 1][l]) continue;
          can[j][k][i] |= can[l][k ^ 1][i - 1];
        }
  for (int i = 1; i <= N; ++i)
    if (can[i][0][60].any()) puts("-1"), exit(0);
  memset(best, -1, sizeof(best));
  for (int i = 1; i <= N; ++i) ans = max(ans, dfs(i, 1));
  if (ans > 1000000000000000000LL) ans = -1;
  printf("%I64d\n", ans);
  return 0;
}
