#include <bits/stdc++.h>
const long long big = 151;
long long n, m, t, ans = 0x3f3f3f3f;
long long dis[big];
std::bitset<big> v;
std::queue<long long> q;
struct _Edge {
  long long u, v, w;
  inline bool operator<(const _Edge &another) const { return w < another.w; }
} e[big];
struct _Matrix {
  std::bitset<big> a[big];
  inline _Matrix operator*(const _Matrix &another) const {
    _Matrix b;
    for (register int i(0); i < n; ++i)
      for (register int j(0); j < n; ++j)
        if (a[i][j]) b.a[i] |= another.a[j];
    return b;
  }
} A;
inline std::bitset<big> BitsetMul(std::bitset<big> a, _Matrix b) {
  std::bitset<big> c;
  for (register int i(0); i < n; ++i) c[i] = (a & b.a[i]).any();
  return c;
}
inline void FastPow(_Matrix A, long long b, std::bitset<big> &c) {
  for (; b; b >>= 1, A = A * A)
    if (b & 1) c = BitsetMul(c, A);
}
inline long long read() {
  char c(getchar());
  long long f(1), x(0);
  for (; !isdigit(c); (c == '-') && (f = -1), c = getchar())
    ;
  for (; isdigit(c); x = (x << 1) + (x << 3) + (c ^ 48), c = getchar())
    ;
  return f * x;
}
int main(void) {
  n = read(), m = read();
  for (register int i(1); i <= m; ++i)
    e[i].u = read() - 1, e[i].v = read() - 1, e[i].w = read();
  std::sort(e + 1, e + 1 + m);
  v[0] = 1;
  for (register int i(1); i <= m; ++i) {
    if (e[i].w >= ans) break;
    long long times = e[i].w - t;
    FastPow(A, times, v);
    A.a[e[i].v][e[i].u] = 1;
    t = e[i].w;
    for (register int x(1); x <= n; ++x)
      if (v[x - 1])
        q.push(x), dis[x] = 0;
      else
        dis[x] = 0x3f3f3f3f;
    while (!q.empty()) {
      long long u = q.front();
      q.pop();
      for (register int to(1); to <= n; ++to)
        if (A.a[to - 1][u - 1] && dis[to] == 0x3f3f3f3f)
          dis[to] = dis[u] + 1, q.push(to);
    }
    ans = std::min(ans, t + dis[n]);
  }
  if (ans == 0x3f3f3f3f)
    printf("Impossible\n");
  else
    printf("%lld\n", ans);
  return 0;
}
