#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') {
      f = -f;
    }
  } while (ch < '0' || ch > '9');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return x * f;
}
struct ask {
  int x, y, z;
} q[155];
int n, c, m;
bool can[55][210][210];
struct mat {
  bool a[210][210];
  mat() { memset(a, false, sizeof(a)); }
  void print() {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (a[i][j]) {
          printf("1 ");
        } else {
          printf("0 ");
        }
      }
      puts("");
    }
    puts("");
  }
};
int ti;
mat operator*(const mat &a, const mat &b) {
  mat c;
  bitset<210> ba[210], bb[210];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      ba[i][j] = a.a[i][j];
      bb[i][j] = b.a[j][i];
    }
  }
  for (int i = 1; i <= n; i++) {
    if (ba[i].any()) {
      for (int j = 1; j <= n; j++) {
        c.a[i][j] = (ba[i] & bb[j]).any();
      }
    }
  }
  return c;
}
mat pw(mat x, int y) {
  mat res;
  for (int i = 1; i <= n; i++) {
    res.a[i][i] = 1;
  }
  while (y) {
    if (y & 1) {
      res = res * x;
    }
    x = x * x;
    y >>= 1;
  }
  return res;
}
bool cmp(ask x, ask y) { return x.z < y.z; }
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= m; i++) {
    q[i].x = read();
    q[i].y = read();
    q[i].z = read();
  }
  sort(q + 1, q + m + 1, cmp);
  if (q[1].z) {
    puts("Impossible");
    return 0;
  }
  mat a;
  mat now;
  now.a[1][1] = true;
  a.a[n][n] = true;
  for (int k = 1; k <= m; k++) {
    a.a[q[k].x][q[k].y] = true;
    mat tmp;
    int y = q[k + 1].z - q[k].z;
    if (k == m) {
      y = n;
    }
    tmp = now * pw(a, y);
    if (tmp.a[1][n]) {
      int ans = q[k].z;
      while (!now.a[1][n]) {
        ans++;
        now = now * a;
      }
      printf("%d\n", ans);
      return 0;
    }
    now = tmp;
  }
  puts("Impossible");
  return 0;
}
