#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const long long INF = 1e18 + 1;
int n, m;
long long dp[2][2][N], ll = 1;
bitset<504> f[2][2][N];
long long sum(long long a, long long b) {
  if (a + b > INF)
    return INF;
  else
    return a + b;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y, t;
    scanf("%d %d %d", &x, &y, &t);
    f[0][t][x][y] = true;
    dp[0][t][x] = 1;
  }
  for (int t = 0; t <= 60; t++) {
    int x = t % 2;
    for (int c = 0; c <= 1; c++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) f[!x][c][i][j] = false;
    for (int c = 0; c <= 1; c++)
      for (int i = 1; i <= n; i++) {
        dp[!x][c][i] = max(dp[!x][c][i], dp[x][c][i]);
        for (int j = 1; j <= n; j++) {
          if (f[x][c][i][j]) {
            f[!x][c][i] |= f[x][!c][j];
            dp[!x][c][i] = max(dp[!x][c][i], sum((ll << t), dp[x][!c][j]));
            if (f[0][0][1][2]) i++, --i;
          }
        }
      }
  }
  long long res = dp[1][0][1];
  if (res == INF)
    printf("-1");
  else
    printf("%I64d", res);
  return 0;
}
