#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "avx,avx2,fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
long long MOD = 1e9 + 7;
const int N = 152;
vector<bitset<N> > mat(N);
vector<bitset<N> > cur(N);
vector<bitset<N> > mul(vector<bitset<N> > a, vector<bitset<N> > b) {
  vector<bitset<N> > ans(N);
  for (int i = 0; i < N; i++) {
    for (int k = 0; k < N; k++) {
      if (a[i][k]) ans[i] |= b[k];
    }
  }
  return ans;
}
vector<bitset<N> > e(N);
void init_mat() {
  for (int i = 0; i < N; i++) {
    e[i][i] = true;
  }
}
vector<bitset<N> > st(vector<bitset<N> > a, long long n) {
  if (n == 0) return e;
  if (n % 2 == 1)
    return mul(st(a, n - 1), a);
  else {
    vector<bitset<N> > b = st(a, n / 2);
    return mul(b, b);
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),
      cout << fixed << setprecision(20);
  long long n, m;
  cin >> n >> m;
  init_mat();
  vector<pair<long long, pair<long long, long long> > > mem(m);
  for (int i = 0; i < m; i++) {
    cin >> mem[i].second.first >> mem[i].second.second >> mem[i].first;
    mem[i].second.first--;
    mem[i].second.second--;
  }
  sort(mem.begin(), mem.end());
  if (mem[0].first != 0) {
    cout << "Impossible";
    return 0;
  }
  bitset<N> can;
  can[0] = true;
  for (int ii = 0; ii < m; ii++) {
    long long u = mem[ii].second.first, v = mem[ii].second.second;
    mat[u][v] = true;
    long long d[N][N];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        d[i][j] = mat[i][j];
        if (!mat[i][j]) {
          d[i][j] = MOD;
        }
      }
    }
    for (int k = 0; k < n; ++k)
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    long long anss = MOD;
    for (int i = 0; i < n; i++) {
      if (can[i]) {
        anss = min(anss, d[i][n - 1]);
      }
    }
    if (anss < MOD / 2) {
      cout << anss + mem[ii].first;
      return 0;
    }
    if (ii < m - 1)
      cur = st(mat, mem[ii + 1].first - mem[ii].first);
    else
      cur = mat;
    bitset<N> can2;
    for (int i1 = 0; i1 < N; i1++) {
      for (int i2 = 0; i2 < N; i2++) {
        if (can[i1] && cur[i1][i2]) {
          can2[i2] = true;
        }
      }
    }
    can = can2;
  }
  cout << "Impossible";
}
