#include <bits/stdc++.h>
using namespace std;
const int maxN = 155;
const int inf32 = 1e9 + maxN;
int n, m;
bool a[maxN][maxN], b[maxN][maxN], lst[maxN][maxN];
int f[maxN][maxN];
pair<int, pair<int, int> > e[maxN];
int ans = inf32;
bitset<maxN> ar[maxN], br[maxN];
void mult(const bool a[maxN][maxN], const bool b[maxN][maxN],
          bool c[maxN][maxN]) {
  for (int i = 1; i <= n; ++i) {
    ar[i].reset();
    for (int j = 1; j <= n; ++j) {
      ar[i][j] = a[i][j];
    }
  }
  for (int j = 1; j <= n; ++j) {
    br[j].reset();
    for (int i = 1; i <= n; ++i) {
      br[j][i] = b[i][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      c[i][j] = (ar[i] & br[j]).any();
    }
  }
  return;
}
void qPow(const bool a[maxN][maxN], int x, bool c[maxN][maxN]) {
  static bool f[maxN][maxN];
  memcpy(f, a, sizeof(f));
  while (x) {
    if (x & 1) {
      mult(c, f, c);
    }
    mult(f, f, f);
    x >>= 1;
  }
  return;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v, d;
    cin >> u >> v >> d;
    e[i] = make_pair(d, make_pair(u, v));
  }
  sort(e + 1, e + m + 1);
  b[1][1] = 1;
  for (int id = 1; id <= m; ++id) {
    qPow(a, e[id].first - e[id - 1].first, b);
    a[e[id].second.first][e[id].second.second] = true;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (a[i][j]) {
          f[i][j] = true;
        } else {
          f[i][j] = inf32;
        }
      }
    }
    for (int k = 1; k <= n; ++k) {
      for (int i = 1; i <= n; ++i) {
        if (i == k) {
          continue;
        }
        for (int j = 1; j <= n; ++j) {
          if (i == j || k == j) {
            continue;
          }
          f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        }
      }
    }
    for (int i = 1; i <= n; ++i) {
      if (b[1][i]) {
        ans = min(ans, e[id].first + f[i][n]);
      }
    }
  }
  if (ans == inf32) {
    cout << "Impossible" << '\n';
  } else {
    cout << ans << '\n';
  }
  return 0;
}
