#include <bits/stdc++.h>
using namespace std;
namespace io {
const int SI = 1 << 21 | 1;
char IB[SI], *IS, *IT, OB[SI], *OS = OB, *OT = OS + SI - 1, c, ch[100];
int f, t;
inline void flush() { fwrite(OB, 1, OS - OB, stdout), OS = OB; }
inline void pc(char x) {
  *OS++ = x;
  if (OS == OT) flush();
}
template <class I>
inline void rd(I &x) {
  for (f = 1, c = (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin),
                              IS == IT ? EOF : *IS++)
                            : *IS++);
       c < '0' || c > '9';
       c = (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin),
                       IS == IT ? EOF : *IS++)
                     : *IS++))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c & 15),
      c = (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin),
                      IS == IT ? EOF : *IS++)
                    : *IS++))
    ;
  x *= f;
}
inline void rds(char *s, int &x) {
  for (c = (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin),
                       IS == IT ? EOF : *IS++)
                     : *IS++);
       c < 33 || c > 126;
       c = (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin),
                       IS == IT ? EOF : *IS++)
                     : *IS++))
    ;
  for (x = 0; c >= 33 && c <= 126;
       s[++x] = c, c = (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin),
                                   IS == IT ? EOF : *IS++)
                                 : *IS++))
    ;
  s[x + 1] = '\0';
}
template <class I>
inline void print(I x, char k = '\n') {
  if (!x) pc('0');
  if (x < 0) pc('-'), x = -x;
  while (x) ch[++t] = x % 10 + '0', x /= 10;
  while (t) pc(ch[t--]);
  pc(k);
}
inline void prints(string s) {
  int x = s.length();
  while (t < x) pc(s[t++]);
  pc('\n'), t = 0;
}
struct Flush {
  ~Flush() { flush(); }
} flusher;
}  // namespace io
using io::print;
using io::prints;
using io::rd;
using io::rds;
const int N = 150;
const long long inf = 1e18;
int n, m;
struct E {
  int x, y, z;
  inline void input() { rd(x), rd(y), rd(z), --x, --y; }
  inline friend bool operator<(E a, E b) { return a.z < b.z; }
} e[N];
long long d[N], ans;
bitset<N> v;
struct mt {
  bitset<N> a[N];
  inline friend bitset<N> operator*(bitset<N> x, mt y) {
    bitset<N> z;
    for (int i = 0; i < n; i++) z[i] = (x & y.a[i]).any();
    return z;
  }
  inline friend mt operator*(mt x, mt y) {
    mt z;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (x.a[i][j]) z.a[i] |= y.a[j];
    return z;
  }
} a;
inline void ksm(mt x, int y, bitset<N> &z) {
  while (y) {
    if (y & 1) z = z * x;
    x = x * x, y >>= 1;
  }
}
int main() {
  rd(n), rd(m);
  for (int i = 0; i < m; i++) e[i].input();
  sort(e, e + m);
  v[0] = 1;
  ans = inf;
  for (int i = 0, t = 0; i < m; i++) {
    if (e[i].z >= ans) break;
    int o = e[i].z - t;
    ksm(a, o, v);
    a.a[e[i].y][e[i].x] = 1;
    t = e[i].z;
    queue<int> q;
    for (int x = 0; x < n; x++)
      if (v[x])
        q.push(x), d[x] = 0;
      else
        d[x] = inf;
    while (q.size()) {
      int x = q.front();
      q.pop();
      for (int y = 0; y < n; y++)
        if (a.a[y][x] && d[y] == inf) d[y] = d[x] + 1, q.push(y);
    }
    ans = min(ans, t + d[n - 1]);
  }
  if (ans == inf)
    prints("Impossible");
  else
    print(ans);
  return 0;
}
