#include <bits/stdc++.h>
using namespace std;
const int N = 155, inf = 0x3f3f3f3f;
struct edge {
  int x, y, d;
  friend inline bool operator<(const edge &a, const edge &b) {
    return a.d < b.d;
  }
} e[N];
int n, m, dis[N][N], ans = inf;
struct matrix {
  bitset<N> c[N];
  matrix() {
    for (int i = 1; i <= n; i++) c[i].reset();
  }
  friend inline matrix operator*(const matrix &a, const matrix &b) {
    matrix res;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (a.c[i][j]) res.c[i] |= b.c[j];
    return res;
  }
} A;
signed main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) A.c[i][i] = 1;
  for (int i = 1; i <= m; i++) cin >> e[i].x >> e[i].y >> e[i].d;
  sort(e + 1, e + m + 1);
  for (int x = 1; x <= m; x++) {
    matrix B;
    for (int i = 1; i < x; i++) B.c[e[i].x][e[i].y] = 1;
    int val = e[x].d - e[x - 1].d;
    for (; val; val >>= 1) {
      if (val & 1) A = A * B;
      B = B * B;
    }
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) dis[i][j] = inf;
    for (int i = 1; i <= n; i++) dis[i][i] = 0;
    for (int i = 1; i <= x; i++) dis[e[i].x][e[i].y] = 1;
    for (int k = 1; k <= n; k++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    for (int i = 1; i <= n; i++)
      if (A.c[1][i]) ans = min(ans, e[x].d + dis[i][n]);
  }
  if (ans < inf)
    cout << ans << endl;
  else
    cout << "Impossible" << endl;
  return 0;
}
