#include <bits/stdc++.h>
using namespace std;
const int maxn = 160;
const int INF = 0x3f3f3f3f;
struct Edge {
  int u, v, w;
  bool operator<(const Edge& tmp) const { return w < tmp.w; }
} e[maxn];
int n, m, cur, ans = INF;
int dis[maxn][maxn];
struct Matrix {
  bitset<maxn> h[maxn], r[maxn];
  inline void insert(int x, int y) {
    h[y].set(x);
    r[x].set(y);
  }
  Matrix operator*(const Matrix& tmp) const {
    Matrix res;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if ((r[i] & tmp.h[j]).count()) res.insert(i, j);
    return res;
  }
  inline void print() {
    for (int i = 1; i <= n; i++, puts(""))
      for (int j = 1; j <= n; j++) printf("%d ", r[i][j] == 1);
  }
} d, res;
inline int read() {
  int x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void power(int b) {
  Matrix base = d;
  while (b) {
    if (b & 1) res = res * base;
    base = base * base;
    b >>= 1;
  }
}
inline void floyed() {
  memset(dis, 0x3f, sizeof(dis));
  for (int i = 1; i <= n; i++) dis[i][i] = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (d.r[i][j]) dis[i][j] = 1;
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  for (int i = 1; i <= n; i++)
    if (res.r[1][i]) {
      ans = min(ans, cur + dis[i][n]);
    }
}
int main() {
  if (fopen("D.in", "r") != NULL) {
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
  }
  n = read(), m = read();
  for (int i = 1; i <= m; i++) {
    e[i].u = read(), e[i].v = read();
    e[i].w = read();
  }
  for (int i = 1; i <= n; i++) res.insert(i, i);
  sort(e + 1, e + m + 1);
  cur = 0;
  for (int i = 1; i <= m; i++) {
    if (e[i].w != cur) {
      power(e[i].w - cur);
      cur = e[i].w;
    }
    d.insert(e[i].u, e[i].v);
    floyed();
  }
  if (ans == INF)
    puts("Impossible");
  else
    printf("%d \n", ans);
  return 0;
}
