#include <bits/stdc++.h>
const long long P = 998244353;
using namespace std;
template <typename T>
inline void ckmax(T &a, T b) {
  (a < b) && (a = b);
}
template <typename T>
inline void ckmin(T &a, T b) {
  (a > b) && (a = b);
}
inline long long mul(long long a, long long b) { return 1ll * a * b % P; }
inline long long add(long long a, long long b) {
  return a + b >= P ? a + b - P : a + b;
}
inline long long sub(long long a, long long b) {
  return a - b >= 0 ? a - b : a - b + P;
}
inline void mulmod(long long &a, long long b) { a = mul(a, b); }
inline void addmod(long long &a, long long b) { ((a += b) >= P) && (a -= P); }
inline void submod(long long &a, long long b) { ((a -= b) < 0) && (a += P); }
inline long long ksm(long long a, long long b) {
  long long ans = 1;
  for (; b; b >>= 1) {
    if (b & 1) ans = 1ll * ans * a % P;
    a = 1ll * a * a % P;
  }
  return ans;
}
inline void fprint(const vector<long long> &f) {
  for (long long i = 0; i < (long long)f.size(); i++)
    fprintf(stderr, "%d ", f[i]);
  fprintf(stderr, "\n");
}
inline long long inv(long long a) { return ksm(a, P - 2); }
namespace FastIO {
const long long SIZE = 1 << 16;
char buf[SIZE], obuf[SIZE], str[64];
long long bi = SIZE, bn = SIZE, opt;
long long read(char *s) {
  while (bn) {
    for (; bi < bn && buf[bi] <= ' '; bi++)
      ;
    if (bi < bn) break;
    bn = fread(buf, 1, SIZE, stdin), bi = 0;
  }
  long long sn = 0;
  while (bn) {
    for (; bi < bn && buf[bi] > ' '; bi++) s[sn++] = buf[bi];
    if (bi < bn) break;
    bn = fread(buf, 1, SIZE, stdin), bi = 0;
  }
  s[sn] = 0;
  return sn;
}
bool read(long long &x) {
  if (x) x = 0;
  long long bf = 0, n = read(str);
  if (!n) return 0;
  long long i = 0;
  if (str[i] == '-') bf = 1, i = 1;
  for (x = 0; i < n; i++) x = x * 10 + str[i] - '0';
  if (bf) x = -x;
  return 1;
}
void write(long long x) {
  if (!x)
    obuf[opt++] = '0';
  else {
    if (x < 0) obuf[opt++] = '-', x = -x;
    long long sn = 0;
    while (x) str[sn++] = x % 10 + '0', x /= 10;
    for (long long i = sn - 1; i >= 0; i--) obuf[opt++] = str[i];
  }
  if (opt >= (SIZE >> 1)) {
    fwrite(obuf, 1, opt, stdout);
    opt = 0;
  }
}
void write(char x) {
  obuf[opt++] = x;
  if (opt >= (SIZE >> 1)) {
    fwrite(obuf, 1, opt, stdout);
    opt = 0;
  }
}
void Fflush() {
  if (opt) fwrite(obuf, 1, opt, stdout);
  opt = 0;
}
};  // namespace FastIO
inline long long read() {
  long long x;
  FastIO::read(x);
  return x;
}
const long long MN = 155;
long long n, m, d[MN];
struct mat {
  bitset<MN> a[MN];
  mat() {
    for (long long i = (1); i <= (n); i++) a[i].reset();
  }
  mat operator*(mat b) {
    mat res;
    for (long long i = (1); i <= (n); i++) {
      for (long long j = (1); j <= (n); j++) {
        if (a[i][j]) {
          res.a[i] |= b.a[j];
        }
      }
    }
    return res;
  }
};
mat ksm(mat a, long long b) {
  mat ans;
  for (long long i = (1); i <= (n); i++) ans.a[i].set(i);
  for (; b; b >>= 1) {
    if (b & 1) ans = ans * a;
    a = a * a;
  }
  return ans;
}
mat trans;
bitset<MN> now, tnow;
struct Edge {
  long long u, v, d;
  bool operator<(const Edge &b) const { return d < b.d; }
} e[MN];
vector<long long> g[MN];
signed main() {
  n = read(), m = read();
  for (long long i = (1); i <= (m); i++) {
    long long u = read(), v = read(), d = read();
    e[i] = (Edge){u, v, d};
  }
  now.set(1);
  sort(e + 1, e + 1 + m);
  long long ans = ((1ll << 60) - 1);
  for (long long t = 1; t <= m; t++) {
    mat tmp = ksm(trans, e[t].d - e[t - 1].d);
    tnow.reset();
    for (long long i = (1); i <= (n); i++) {
      for (long long j = (1); j <= (n); j++) {
        if (now[j] & tmp.a[j][i]) tnow.set(i);
      }
    }
    trans.a[e[t].u][e[t].v] = 1;
    for (long long i = (1); i <= (n); i++) d[i] = ((1ll << 60) - 1);
    now = tnow;
    queue<long long> q;
    g[e[t].u].push_back(e[t].v);
    for (long long i = (1); i <= (n); i++) {
      if (tnow[i]) {
        q.push(i);
        d[i] = 0;
      }
    }
    while (q.size()) {
      long long u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (d[v] > d[u] + 1) {
          d[v] = d[u] + 1;
          q.push(v);
        }
      }
    }
    ckmin(ans, d[n] + e[t].d);
  }
  if (ans >= ((1ll << 60) - 1))
    printf("Impossible\n");
  else
    cout << ans << endl;
  return FastIO::Fflush(), 0;
}
