#include <bits/stdc++.h>
using namespace std;
struct e {
  int l, r, w;
} edge[160];
struct matrix {
  int n, a[160][160];
  matrix() { memset(a, 0, sizeof(a)); }
} I, M, f;
int n, m, i, ans, l, j, k;
int dis[160][160];
bitset<160> s1[160], s2[160];
bool cmp(e a, e b) { return a.w < b.w; }
matrix operator*(const matrix &A, const matrix &B) {
  matrix C;
  C.n = A.n;
  int i, j;
  for (i = 1; i <= A.n; i++) {
    s1[i].reset();
    s2[i].reset();
    for (j = 1; j <= A.n; j++) {
      if (A.a[i][j]) s1[i].set(j);
      if (B.a[j][i]) s2[i].set(j);
    }
  }
  for (i = 1; i <= A.n; i++)
    for (j = 1; j <= A.n; j++)
      if ((s1[i] & s2[j]).count()) C.a[i][j] = 1;
  return C;
}
matrix ksm(int x) {
  matrix ans;
  if (x == 0)
    ans = I;
  else {
    ans = ksm(x / 2);
    ans = ans * ans;
    if (x & 1) ans = ans * M;
  }
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= m; i++) scanf("%d%d%d", &edge[i].l, &edge[i].r, &edge[i].w);
  sort(edge + 1, edge + 1 + m, cmp);
  memset(dis, 63, sizeof(dis));
  for (i = 1; i <= n; i++) {
    dis[i][i] = 0;
    I.a[i][i] = 1;
    f.a[i][i] = 1;
  }
  I.n = f.n = M.n = n;
  ans = dis[0][0];
  for (i = 1; i <= m; i++) {
    f = f * ksm(edge[i].w - l);
    l = edge[i].w;
    M.a[edge[i].l][edge[i].r] = 1;
    for (j = 1; j <= n; j++)
      for (k = 1; k <= n; k++)
        dis[j][k] = min(dis[j][k], dis[j][edge[i].l] + dis[edge[i].r][k] + 1);
    for (j = 1; j <= n; j++)
      if (f.a[1][j]) ans = min(ans, l + dis[j][n]);
  }
  if (ans == dis[0][0])
    printf("Impossible");
  else
    printf("%d\n", ans);
}
