#include <bits/stdc++.h>
using namespace std;
const int MN = 155, inf = 1100000005, mod = 1000000007;
const long long INF = 1000000000000000005LL;
struct matrix {
  bitset<MN> wie[MN], kol[MN];
};
matrix operator*(matrix a, matrix b) {
  matrix res;
  for (int i = 1; i < MN; ++i)
    for (int j = 1; j < MN; ++j)
      res.wie[i][j] = res.kol[j][i] =
          ((a.wie[i] & b.kol[j]).count() > 0 ? 1 : 0);
  return res;
}
matrix zero() {
  matrix res;
  for (int i = 1; i < MN; ++i) res.wie[i][i] = res.kol[i][i] = 1;
  return res;
}
matrix pot(matrix a, int wyk) {
  matrix res = zero();
  while (wyk) {
    if (wyk & 1) res = res * a;
    a = a * a;
    wyk >>= 1;
  }
  return res;
}
pair<int, pair<int, int> > kraw[MN];
vector<int> G[MN];
int used[MN];
queue<int> Q;
int n;
int bfs(int v) {
  Q.push(v);
  for (int i = 1; i <= n; ++i) used[i] = 0;
  used[v] = 1;
  while (!Q.empty()) {
    int cur = Q.front();
    Q.pop();
    for (auto x : G[cur])
      if (!used[x]) {
        used[x] = used[cur] + 1;
        Q.push(x);
      }
  }
  return (used[n] == 0 ? inf : used[n] - 1);
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int a, b, d;
    scanf("%d%d%d", &a, &b, &d);
    kraw[i] = {d, {a, b}};
  }
  sort(kraw + 1, kraw + 1 + m);
  matrix drogi, mozna;
  mozna.kol[1][1] = mozna.wie[1][1] = 1;
  mozna.kol[n][n] = mozna.wie[n][n] = drogi.kol[n][n] = drogi.wie[n][n] = 1;
  int res = inf;
  for (int i = 1; i <= m; ++i) {
    int dif = kraw[i].first - kraw[i - 1].first;
    mozna = mozna * pot(drogi, dif);
    int a = kraw[i].second.first, b = kraw[i].second.second;
    G[a].push_back(b);
    drogi.wie[a][b] = drogi.kol[b][a] = 1;
    for (int j = 1; j <= n; ++j)
      if (mozna.wie[1][j]) res = min(res, kraw[i].first + bfs(j));
  }
  if (res == inf)
    printf("Impossible");
  else
    printf("%d\n", res);
}
