#include <bits/stdc++.h>
using namespace std;
const int MaxN = 153, MaxM = 153;
const int INF = 0x7f7f7f7f;
const long long LINF = 0x7f7f7f7f7f7f7f;
struct edge {
  int u, v, w;
  inline bool operator<(const edge& o) const { return w < o.w; }
} e[MaxM];
int n, m;
struct mat {
  static const int Len = MaxN;
  bitset<Len> m[Len];
  inline bitset<Len>& operator[](int x) { return m[x]; }
  inline mat operator*(mat& x) {
    mat ret;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (m[i][j]) ret[i] |= x[j];
    return ret;
  }
  inline mat& operator*=(mat& x) {
    *this = (*this) * x;
    return *this;
  }
  template <typename T>
  inline mat pow(T x) {
    mat ret, a;
    for (int i = 1; i <= n; i++) ret[i][i] = 1;
    a = *this;
    while (x) {
      if (x & 1) ret *= a;
      a *= a;
      x >>= 1;
    }
    return ret;
  }
};
long long d[MaxN][MaxN];
mat a, g, tmp;
int main() {
  scanf("%d%d", &n, &m);
  int u, v, w;
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &(e[i].u), &(e[i].v), &(e[i].w));
  sort(e + 1, e + m + 1);
  int ts = 0;
  long long ans = LINF;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) d[i][j] = LINF;
  for (int i = 1; i <= n; i++) d[i][i] = 0, a[i][i] = true;
  for (int i = 1; i <= m; i++) {
    u = e[i].u, v = e[i].v, w = e[i].w;
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= n; k++) {
        d[j][k] = min(d[j][k], d[j][u] + d[v][k] + 1);
      }
    tmp = g.pow(w - ts);
    a *= tmp;
    for (int j = 1; j <= n; j++)
      if (a[1][j] && d[j][n] != LINF) ans = min(ans, d[j][n] + w);
    ts = w;
    g[u][v] = true;
  }
  if (ans == LINF) {
    puts("Impossible");
  } else {
    printf("%I64d\n", ans);
  }
  return 0;
}
