#include <bits/stdc++.h>
using namespace std;
const int maxn = 150 + 2;
const int INF = 0x7fffffff;
inline void upmin(int &x, int y) { x = min(x, y); }
int n, m;
struct anode {
  int u, v, t;
  anode() {}
  anode(int _u, int _v, int _t) : u(_u), v(_v), t(_t) {}
} a[maxn];
struct Mat {
  bitset<maxn> num[maxn];
  inline void init() {
    for (int i = 0; i < n; i++) num[i].reset();
  }
  friend Mat operator*(Mat a, Mat b) {
    Mat c;
    c.init();
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < n; k++) {
        if (a.num[i][k]) c.num[i] |= b.num[k];
      }
    }
    return c;
  }
} A, B;
inline Mat ksm(Mat A, int k) {
  Mat B;
  B.init();
  for (int i = 0; i < n; i++) B.num[i][i] = 1;
  while (k) {
    if (k & 1) B = B * A;
    A = A * A;
    k >>= 1;
  }
  return B;
}
inline bool cmpt(anode a, anode b) { return a.t < b.t; }
int Ans;
inline void calc_ans(int id) {
  Mat now = A;
  if (A.num[0][n - 1]) upmin(Ans, a[id].t);
  for (int i = 1; i <= n; i++) {
    now = now * B;
    if (now.num[0][n - 1]) upmin(Ans, a[id].t + i);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v, t;
    scanf("%d%d%d", &u, &v, &t);
    a[i] = anode(u, v, t);
  }
  sort(a + 1, a + m + 1, cmpt);
  A.init();
  B.init();
  Ans = INF;
  A.num[0][0] = 1;
  A = A * ksm(B, a[1].t);
  for (int i = 1; i <= m; i++) {
    int u = a[i].u, v = a[i].v;
    u--;
    v--;
    B.num[u][v] = 1;
    calc_ans(i);
    if (i + 1 <= m) A = A * ksm(B, a[i + 1].t - a[i].t);
  }
  if (Ans == INF)
    puts("Impossible");
  else
    printf("%d\n", Ans);
  return 0;
}
