#include <bits/stdc++.h>
using namespace std;
const int UNDEF = -1;
const int INF = 2e9;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
const int mn = 150;
vector<pair<int, pair<int, int> > > ve;
int va[mn], vb[mn], vd[mn];
int n, m;
typedef struct matt {
  bitset<mn> t[mn];
  void reset() {
    for (int x = 0; x < n; x++) t[x].reset();
  }
} mat;
typedef struct vect {
  bitset<mn> t;
  void reset() { t.reset(); }
} vec;
bitset<mn> tmp[mn];
mat mul(mat a, mat b) {
  mat res;
  for (int x = 0; x < n; x++) tmp[x].reset();
  for (int x = 0; x < n; x++)
    for (int y = 0; y < n; y++) {
      tmp[y][x] = b.t[x][y];
    }
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < n; y++) {
      res.t[x][y] = (a.t[x] & tmp[y]).any();
    }
  }
  return res;
}
mat go(int l, int k) {
  vector<int> v;
  while (l > 0) {
    if (l & 1) {
      v.push_back(1);
      l--;
    } else {
      v.push_back(0);
      l /= 2;
    }
  }
  reverse(v.begin(), v.end());
  mat res;
  res.reset();
  for (int x = 0; x < n; x++) res.t[x][x] = true;
  mat orig;
  orig.reset();
  for (int i = 0; i <= k; i++) {
    orig.t[va[i]][vb[i]] = true;
  }
  for (auto &w : v) {
    if (w == 0) {
      res = mul(res, res);
    } else {
      res = mul(res, orig);
    }
  }
  return res;
}
vec mulv(vec inp, int k) {
  vec res;
  res.reset();
  for (int i = 0; i <= k; i++) {
    if (inp.t[va[i]]) res.t[vb[i]] = true;
  }
  return res;
}
vec mulv2(vec inp, mat a) {
  vec res;
  res.reset();
  for (int x = 0; x < n; x++)
    for (int y = 0; y < n; y++) {
      if (inp.t[x] && a.t[x][y]) res.t[y] = true;
    }
  return res;
}
bool cur[mn], nxt[mn];
int canhit(vec res, int k) {
  if (res.t[n - 1]) return 0;
  for (int i = 0; i <= n; i++) {
    res = mulv(res, k);
    if (res.t[n - 1]) return i + 1;
  }
  return INF;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b, d;
    scanf("%d%d%d", &a, &b, &d);
    --a;
    --b;
    ve.push_back(make_pair(d, make_pair(a, b)));
  }
  sort(ve.begin(), ve.end());
  for (int i = 0; i < m; i++) {
    vd[i] = ve[i].first;
    va[i] = ve[i].second.first;
    vb[i] = ve[i].second.second;
  }
  vec res;
  res.reset();
  res.t[0] = true;
  int final = INF;
  int lastd = 0;
  for (int i = 0; i < m; i++) {
    int changed = vd[i] - lastd;
    lastd = vd[i];
    res = mulv2(res, go(changed, i - 1));
    int got = canhit(res, i);
    if (got < INF) {
      chkmin(final, got + vd[i]);
    }
  }
  if (final >= INF)
    printf("Impossible\n");
  else
    printf("%d\n", final);
}
