#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
template <class T>
inline bool chkmin(T& a, T b) {
  return a > b ? a = b, true : false;
}
template <class T>
inline bool chkmax(T& a, T b) {
  return a < b ? a = b, true : false;
}
const int maxN = 155;
int N, M;
struct Matrix {
  bitset<maxN> col[maxN];
  bitset<maxN> row[maxN];
  inline Matrix() {}
  inline void init() {
    for (int i = (1), _end = (N); i <= _end; ++i) col[i] = row[i] = 0;
  }
  inline Matrix operator*(const Matrix x) const {
    static Matrix ret;
    ret.init();
    for (int i = (1), _end = (N); i <= _end; ++i)
      for (int j = (1), _end = (N); j <= _end; ++j) {
        bitset<maxN> lover;
        lover = row[i] & x.col[j];
        ret.row[i][j] = ret.col[j][i] = (lover != 0);
      }
    return ret;
  }
  inline Matrix operator^(int t) const {
    static Matrix ret, base;
    ret.init();
    base = *this;
    for (int i = (1), _end = (N); i <= _end; ++i)
      ret.row[i][i] = ret.col[i][i] = 1;
    while (t) {
      if (t & 1) ret = ret * base;
      base = base * base;
      t >>= 1;
    }
    return ret;
  }
} A, T, P;
struct Edge {
  int u, v, w;
} ed[maxN];
bool cmp(const Edge& x, const Edge& y) { return x.w < y.w; }
void init() {
  scanf("%d%d", &N, &M);
  for (int i = (1), _end = (M); i <= _end; ++i) {
    scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w);
  }
  sort(ed + 1, ed + M + 1, cmp);
}
int dis[maxN][maxN];
void solve() {
  A.init();
  T.init();
  for (int i = (1), _end = (N); i <= _end; ++i) A.row[i][i] = A.col[i][i] = 1;
  memset(dis, +oo, sizeof(dis));
  int idx = 1;
  while (ed[idx].w == 0) {
    int i = ed[idx].u, j = ed[idx].v;
    T.row[i][j] = T.col[j][i] = 1;
    dis[i][j] = 1;
    ++idx;
  }
  for (int k = (1), _end = (N); k <= _end; ++k)
    for (int t = (1), _end = (N); t <= _end; ++t)
      for (int p = (1), _end = (N); p <= _end; ++p)
        chkmin(dis[t][p], dis[t][k] + dis[k][p]);
  if (dis[1][N] != +oo) {
    printf("%d\n", dis[1][N]);
    return;
  }
  for (int i = (idx), _end = (M); i <= _end; ++i) {
    P = (T ^ (ed[i].w - ed[i - 1].w));
    A = A * P;
    dis[ed[i].u][ed[i].v] = 1;
    for (int k = (1), _end = (N); k <= _end; ++k)
      for (int j = (1), _end = (N); j <= _end; ++j)
        for (int t = (1), _end = (N); t <= _end; ++t)
          chkmin(dis[j][t], dis[j][k] + dis[k][t]);
    int ans = +oo;
    for (int j = (1), _end = (N); j <= _end; ++j)
      if (A.row[1][j] == 1) {
        chkmin(ans, dis[j][N]);
      }
    if (ans != +oo) {
      printf("%d\n", ed[i].w + ans);
      return;
    }
    T.row[ed[i].u][ed[i].v] = T.col[ed[i].v][ed[i].u] = 1;
  }
  puts("Impossible");
}
int main() {
  init();
  solve();
  return 0;
}
