#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f = ch == '-', ch = getchar();
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
const int N = 155, M = 155;
int n, m;
struct Mat {
  bitset<N> v[N];
  Mat() {}
  Mat(int x) {
    for (int i = (1); i <= (n); i++) v[i].reset();
    if (x)
      for (int i = (1); i <= (n); i++) v[i][i] = 1;
  }
  friend Mat operator*(Mat a, Mat b) {
    Mat c(0);
    for (int i = (1); i <= (n); i++)
      for (int k = (1); k <= (n); k++)
        if (a.v[i][k]) c.v[i] |= b.v[k];
    return c;
  }
  void Out() {
    printf("Matrix {\n");
    for (int i = (1); i <= (n); i++) {
      printf("    ");
      for (int j = (1); j <= (n); j++) putchar('0' + v[i][j]);
      puts("");
    }
    puts("}\n");
  }
} pre, mat(0), st[35];
struct Edge {
  int x, y, d;
} e[M];
bool cmp(Edge a, Edge b) { return a.d < b.d; }
int main() {
  n = read(), m = read();
  pre = Mat(1);
  for (int i = (1); i <= (m); i++)
    e[i].x = read(), e[i].y = read(), e[i].d = read();
  m++;
  e[m].x = n, e[m].y = n, e[m].d = 0;
  m++;
  e[m].x = n, e[m].y = n, e[m].d = 1.05e9;
  sort(e + 1, e + m + 1, cmp);
  int now = 0;
  for (int i = (1); i <= (m); i++) {
    int x = e[i].x, y = e[i].y, d = e[i].d;
    if (d == now) {
      mat.v[x][y] = 1;
      continue;
    }
    int c = 0;
    st[c] = mat;
    while ((1 << (c + 1)) <= d) c++, st[c] = st[c - 1] * st[c - 1];
    int ans = d + 1;
    for (int i = (c); i >= (0); i--) {
      if (now + (1 << i) > d) continue;
      Mat tmp = pre * st[i];
      if (tmp.v[1][n])
        ans = min(ans, now + (1 << i));
      else {
        now += 1 << i;
        pre = tmp;
      }
    }
    if (ans <= d) return printf("%d\n", ans), 0;
    mat.v[x][y] = 1;
  }
  puts("Impossible");
  return 0;
}
