#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
int n, m;
long long d[155];
bitset<155> vst;
struct Edge {
  int x, y, b;
  bool operator<(const Edge &tar) const { return b < tar.b; }
} e[155];
struct Matrix {
  bitset<155> M[155];
  Matrix operator*(const Matrix b) {
    Matrix c;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        if (M[i][j]) c.M[i] |= b.M[j];
    return c;
  }
} mp;
void mul(bitset<155> &x, Matrix y) {
  bitset<155> z;
  for (int i = 1; i <= n; ++i) z[i] = (x & y.M[i]).any();
  x = z;
}
void ksm(Matrix x, int y, bitset<155> &z) {
  while (y) {
    if (y & 1) mul(z, x);
    x = x * x;
    y >>= 1;
  }
}
queue<int> q;
void bfs() {
  for (int i = 1; i <= n; ++i)
    if (vst[i])
      q.push(i), d[i] = 0;
    else
      d[i] = 1e18;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int y = 1; y <= n; ++y)
      if (mp.M[y][x] && d[y] == 1e18) d[y] = d[x] + 1, q.push(y);
  }
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= m; ++i) e[i] = (Edge){read(), read(), read()};
  sort(e + 1, e + m + 1);
  int pre = 0;
  long long ans = 1e18;
  vst[1] = 1;
  for (int i = 1; i <= m; ++i) {
    if (e[i].b >= ans) break;
    int res = e[i].b - pre;
    ksm(mp, res, vst);
    pre = e[i].b;
    mp.M[e[i].y][e[i].x] = 1;
    bfs();
    ans = min(ans, pre + d[n]);
  }
  if (ans == 1e18)
    puts("Impossible");
  else
    cout << ans;
}
