#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &n) {
  n = 0;
  T f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (isdigit(c)) n = n * 10 + c - '0', c = getchar();
  n *= f;
}
template <typename T>
void write(T n) {
  if (n < 0) putchar('-'), n = -n;
  if (n > 9) write(n / 10);
  putchar(n % 10 + '0');
}
int n, m;
struct edge {
  int x, y, t;
  friend bool operator<(edge a, edge b) { return a.t < b.t; }
} e[205];
struct Matrix {
  bitset<205> a[205];
  Matrix() {
    for (int i = 0; i < 205; i++) a[i].reset();
  }
  friend Matrix operator*(Matrix a, Matrix b) {
    Matrix c;
    for (int i = 1; i <= n; i++) {
      for (int k = 1; k <= n; k++) {
        if (a.a[i][k]) c.a[i] |= b.a[k];
      }
    }
    return c;
  }
} g, a;
Matrix qpow(Matrix a, int t) {
  Matrix res;
  for (int i = 1; i <= n; i++) res.a[i][i] = 1;
  while (t) {
    if (t & 1) res = res * a;
    a = a * a;
    t >>= 1;
  }
  return res;
}
long long dis[205];
void bfs() {
  queue<int> q;
  for (int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f3f3f3f3f;
  for (int i = 1; i <= n; i++)
    if (a.a[1][i]) q.push(i), dis[i] = 0;
  while (!q.empty()) {
    int t = q.front();
    q.pop();
    for (int i = 1; i <= n; i++) {
      if (g.a[t][i] && dis[i] == 0x3f3f3f3f3f3f3f3f) {
        dis[i] = dis[t] + 1;
        q.push(i);
      }
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    read(e[i].x), read(e[i].y), read(e[i].t);
  }
  sort(e + 1, e + m + 1);
  a.a[1][1] = 1;
  memset(dis, 0x3f, sizeof(dis));
  long long t = 0, ans = 0x3f3f3f3f3f3f3f3f;
  for (int i = 1; i <= m; i++) {
    int x = e[i].t - t;
    t = e[i].t;
    a = a * qpow(g, x);
    g.a[e[i].x][e[i].y] = 1;
    if (i == m || e[i].t != e[i + 1].t) bfs();
    ans = min(ans, t + dis[n]);
  }
  if (ans == 0x3f3f3f3f3f3f3f3f)
    puts("Impossible");
  else
    cout << ans << endl;
  return 0;
}
