#include <bits/stdc++.h>
using namespace std;
namespace FGF {
int n, m;
const int N = 155;
const int INF = 0x3f3f3f3f;
int ans = INF, now, lst;
struct EDG {
  int u, v, w;
} E[N];
struct matrx {
  int r, c;
  bitset<N> a[N];
  matrx() {}
  matrx(int _r, int _c) : r(_r), c(_c) {
    for (int i = 1; i <= r; i++) a[i].reset();
  }
  matrx operator*(const matrx &x) {
    matrx s = matrx(r, x.c);
    for (int j = 1; j <= x.r; j++)
      for (int i = 1; i <= r; i++)
        if (a[i][j]) s.a[i] = s.a[i] | x.a[j];
    return s;
  }
} A, B;
bool cmp(EDG x, EDG y) { return x.w < y.w; }
matrx qpow(matrx x, int y, matrx &s) {
  while (y) {
    if (y & 1) s = s * x;
    x = x * x;
    y >>= 1;
  }
  return s;
}
queue<int> q;
int dis[N];
void work() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
  sort(E + 1, E + m + 1, cmp);
  A = matrx(1, n), A.a[1][1] = 1, B = matrx(n, n);
  for (int i = 1; i <= m; i++) {
    if (E[i].w > ans) break;
    lst = now, now = E[i].w;
    qpow(B, now - lst, A);
    B.a[E[i].u][E[i].v] = 1;
    while (q.size()) q.pop();
    for (int j = 1; j <= n; j++) {
      if (A.a[1][j])
        q.push(j), dis[j] = 0;
      else
        dis[j] = INF;
    }
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (int v = 1; v <= n; v++)
        if (B.a[u][v] && dis[v] == INF) dis[v] = dis[u] + 1, q.push(v);
      if (dis[n] != INF) ans = min(ans, now + dis[n]);
    }
  }
  if (ans == INF)
    puts("Impossible");
  else
    printf("%d\n", ans);
}
}  // namespace FGF
int main() {
  FGF::work();
  return 0;
}
