#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
void read(long long &x) {
  char ch = getchar();
  x = 0;
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
const long long N = 155;
struct edge {
  long long u, v, d;
  bool operator<(const edge &x) const { return d < x.d; }
} p[N];
long long n, m, res = 1e12, d[N], in[N];
struct mat {
  bitset<N> a[N];
  void clear() {
    for (long long i = 1; i <= n; ++i) a[i].reset();
  }
  mat operator*(const mat &x) const {
    mat t;
    t.clear();
    for (long long k = 1; k <= n; ++k)
      for (long long i = 1; i <= n; ++i)
        if (a[i][k]) t.a[i] |= x.a[k];
    return t;
  }
} k, qwq, t;
void work(long long y) {
  t = k;
  for (; y; y >>= 1, t = t * t)
    if (y & 1) qwq = qwq * t;
}
vector<long long> to[N];
queue<long long> q;
void calc(long long now) {
  memset(in, 0, sizeof(in));
  memset(d, 0x3f, sizeof(d));
  for (long long i = 1; i <= n; ++i)
    if (qwq.a[1][i]) q.push(i), d[i] = now, in[i] = 1;
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    in[u] = 0;
    for (long long i = 0, v; i < to[u].size(); ++i)
      if (d[v = to[u][i]] > d[u] + 1) {
        d[v] = d[u] + 1;
        if (!in[v]) q.push(v), in[v] = 1;
      }
  }
  res = min(res, d[n]);
}
signed main() {
  read(n), read(m);
  for (long long i = 1; i <= m; ++i) read(p[i].u), read(p[i].v), read(p[i].d);
  sort(p + 1, p + m + 1);
  long long la = 0;
  qwq.a[1][1] = 1;
  for (long long i = 1; i <= m; ++i) {
    if (p[i].d >= res) break;
    work(p[i].d - la);
    for (long long j = i; j <= m; ++j) {
      if (p[j].d == p[i].d) {
        to[p[j].u].push_back(p[j].v);
        k.a[p[j].u][p[j].v] = 1;
      } else {
        i = j - 1;
        break;
      }
    }
    calc(p[i].d);
    la = p[i].d;
  }
  if (res > 1e11) return puts("Impossible"), 0;
  return printf("%lld\n", res), 0;
}
