#include <bits/stdc++.h>
using namespace std;
const int N = 160, inf = (1LL << 31) - 1;
int d[N * N], a[N][N];
struct mat {
  bool a[N][N];
} T, A, C, f[32];
int ta[N][6], tb[6][N];
mat operator*(const mat &a, const mat &b) {
  for (int i = 1; i <= 150; i++)
    for (int c = 1, j = 1; c <= 5; c++, j += 30) {
      ta[i][c] = 0;
      for (int k = 0; k <= 29; k++)
        if (a.a[i][j + k]) ta[i][c] |= 1 << k;
    }
  for (int i = 1; i <= 150; i++)
    for (int c = 1, j = 1; c <= 5; c++, j += 30) {
      tb[c][i] = 0;
      for (int k = 0; k <= 29; k++)
        if (b.a[j + k][i]) tb[c][i] |= 1 << k;
    }
  for (int i = 1; i <= 150; i++)
    for (int j = 1; j <= 150; j++) {
      C.a[i][j] = false;
      for (int k = 1; k <= 5; k++) C.a[i][j] |= (ta[i][k] & tb[k][j]) > 0;
    }
  return C;
}
mat tmp;
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) a[i][j] = inf;
  for (int i = 1; i <= m; i++) {
    int x, y, d;
    scanf("%d%d%d", &x, &y, &d);
    a[x][y] = min(a[x][y], d);
  }
  int l = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (a[i][j] <= inf) d[++l] = a[i][j];
  sort(d + 1, d + l + 1);
  l = (int)(unique(d + 1, d + l + 1) - d) - 1;
  int ans = 0;
  d[l + 1] = inf;
  T.a[1][1] = true;
  A.a[n][n] = true;
  for (int t = 1; t <= l; t++)
    if (d[t] < inf) {
      if (t == 1 && d[t] != 0) break;
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          if (a[i][j] == d[t]) A.a[i][j] = true;
      f[0] = A;
      for (int i = 1; i <= 30; i++)
        if (ans <= d[t + 1] - (1 << i)) f[i] = f[i - 1] * f[i - 1];
      for (int i = 30; i >= 0; i--)
        if (ans <= d[t + 1] - (1 << i)) {
          tmp = T * f[i];
          if (!tmp.a[1][n]) T = tmp, ans += 1 << i;
        }
      if (ans < d[t + 1]) {
        printf("%d\n", ans + 1);
        return 0;
      }
    }
  printf("Impossible\n");
  return 0;
}
