#include <bits/stdc++.h>
using namespace std;
const int maxn = 155, maxm = 155;
int i, j, k, m, n, t, ans;
int dis[maxn][maxn];
struct matrix {
  int len, wid;
  bitset<maxn> mt[maxn];
} now, g;
struct edge {
  int x, y, d;
} e[maxm];
inline int cmp(edge a, edge b) { return a.d < b.d; }
matrix mul(matrix a, matrix b) {
  matrix res;
  res.len = a.len, res.wid = b.wid;
  for (int i = 1; i <= res.len; i++)
    for (int j = 1; j <= res.wid; j++) res.mt[i][j] = 0;
  for (int k = 1; k <= a.wid; k++)
    for (int i = 1; i <= a.len; i++)
      if (a.mt[i][k]) res.mt[i] |= b.mt[k];
  return res;
}
matrix calc(matrix a, int b, matrix res) {
  while (b) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a), b >>= 1;
  }
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].d);
  sort(e + 1, e + 1 + m, cmp);
  ans = 0x3f3f3f3f;
  now.len = n, now.wid = n;
  for (i = 1; i <= n; i++) now.mt[i][i] = 1;
  g.len = n, g.wid = n;
  for (t = 1; t <= m; t++) {
    now = calc(g, e[t].d - e[t - 1].d, now);
    g.mt[e[t].x][e[t].y] = 1;
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++) {
        if (g.mt[i][j] == 0)
          dis[i][j] = i == j ? 0 : 0x3f3f3f3f;
        else
          dis[i][j] = g.mt[i][j];
      }
    for (k = 1; k <= n; k++)
      for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
          dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    for (i = 1; i <= n; i++)
      if (now.mt[1][i]) ans = min(ans, e[t].d + dis[i][n]);
  }
  if (ans == 0x3f3f3f3f)
    puts("Impossible");
  else
    printf("%d\n", ans);
  return 0;
}
