#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
}
using namespace std;
inline void MIN(int &a, int b) {
  if (b < a) a = b;
}
inline void MAX(int &a, int b) {
  if (b > a) a = b;
}
int n, m;
struct Edge {
  int u, v, d;
} E[157];
bool cmp(const Edge &a, const Edge &b) { return a.d < b.d; }
struct matrix {
  int n;
  bitset<157> b[157];
  matrix(int x) {
    n = x;
    for (int i = 1; i <= n; ++i) b[i].reset();
  }
  matrix operator*(const matrix a) const {
    matrix mt(n);
    for (int i = 1; i <= n; ++i)
      for (int k = 1; k <= a.n; ++k)
        if (b[i][k]) mt.b[i] = mt.b[i] | a.b[k];
    return mt;
  }
};
struct edge {
  int nxt, to;
} e[157];
int head[157], ecnt;
inline void addedge(int from, int to) {
  e[++ecnt] = (edge){head[from], to};
  head[from] = ecnt;
}
int dep[157], que[157], front, rear;
inline int bfs(matrix mt) {
  memset(dep, 0x3f, sizeof(dep));
  dep[n] = 0;
  front = rear = 0;
  que[++rear] = n;
  while (front < rear) {
    int cur = que[++front];
    for (int i = head[cur]; i; i = e[i].nxt) {
      int to = e[i].to;
      if (dep[to] <= 1e9) continue;
      dep[to] = dep[cur] + 1;
      que[++rear] = to;
    }
  }
  int res = 1e9 + 10000;
  for (int i = 1; i <= n; ++i)
    if (mt.b[1][i]) MIN(res, dep[i]);
  return res;
}
inline void Quickpow(matrix &a, matrix b, int k) {
  while (k) {
    if (k & 1) a = a * b;
    b = b * b;
    k >>= 1;
  }
}
inline void work() {
  sort(E + 1, E + 1 + m, cmp);
  matrix A(1), B(n);
  A.b[1][1] = 1;
  int nw = 0, ans = 2e9;
  for (int i = 1; i <= m; ++i) {
    int nwd = E[i].d;
    Quickpow(A, B, nwd - nw);
    B.b[E[i].u][E[i].v] = 1;
    addedge(E[i].v, E[i].u);
    nw = nwd;
    MIN(ans, nw + bfs(A));
  }
  if (ans > 1e9 + 1000)
    puts("Impossible");
  else
    printf("%d\n", ans);
}
int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    read(E[i].u), read(E[i].v), read(E[i].d);
  }
  work();
  return 0;
}
