#include <bits/stdc++.h>
using namespace std;
int n, m;
const int MAX = 151;
const int INF = int(1e9);
typedef bool mx[MAX][MAX];
typedef bool row[MAX];
mx g;
row reach;
struct Edge {
  Edge() {}
  Edge(int _f, int _t, int _d) : f(_f), t(_t), d(_d) {}
  int f, t, d;
};
Edge e[MAX * MAX];
int ne = 0;
void mul(const mx a, const mx b, mx r) {
  int rb[MAX][MAX] = {0};
  int nrb[MAX] = {0};
  for (size_t i = 0; i < n; i++)
    for (size_t j = 0; j < n; j++)
      if (b[i][j]) rb[i][nrb[i]++] = j;
  memset(r, 0, sizeof(mx));
  for (size_t i = 0; i < n; i++)
    for (size_t k = 0; k < n; k++)
      if (a[i][k])
        for (size_t j = 0; j < nrb[k]; j++)
          r[i][rb[k][j]] |= a[i][k] & b[k][rb[k][j]];
}
void mul(const row a, const mx b, row r) {
  memset(r, 0, sizeof(row));
  for (size_t j = 0; j < n; j++)
    for (size_t k = 0; k < n; k++) r[j] |= a[k] & b[k][j];
}
void ones(mx a) {
  memset(a, 0, sizeof(mx));
  for (size_t i = 0; i < n; i++) a[i][i] = 1;
}
void bin_pow(const mx a, int p, mx r) {
  ones(r);
  mx b;
  memcpy(b, a, sizeof(b));
  mx t;
  while (p) {
    if (p & 1) {
      mul(r, b, t);
      memcpy(r, t, sizeof(mx));
    }
    mul(b, b, t);
    memcpy(b, t, sizeof(mx));
    p >>= 1;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (size_t i = 0; i < m; i++) {
    int a, b, d;
    scanf("%d%d%d", &a, &b, &d);
    a--, b--;
    e[ne++] = Edge(a, b, d);
  }
  sort(e, e + ne, [](const Edge &a, const Edge &b) { return a.d < b.d; });
  reach[0] = true;
  int t = 0;
  for (size_t i = 0; i < ne;) {
    int td = e[i].d;
    mx rpow;
    bin_pow(g, td - t, rpow);
    t = td;
    row rmul;
    mul(reach, rpow, rmul);
    memcpy(reach, rmul, sizeof(row));
    for (; i < ne && e[i].d == td; i++) g[e[i].f][e[i].t] = 1;
    int d[MAX];
    for (size_t j = 0; j < n; j++) d[j] = reach[j] ? 0 : INF;
    row u;
    memset(u, 0, sizeof(row));
    for (size_t j = 0; j < n; j++) {
      int v = -1;
      for (int k = 0; k < n; k++)
        if (!u[k] && (v == -1 || d[k] < d[v])) v = k;
      if (d[v] == INF) break;
      u[v] = true;
      for (size_t l = 0; l < n; l++)
        if (g[v][l] && d[l] > d[v] + 1) d[l] = d[v] + 1;
    }
    if (u[n - 1]) {
      printf("%d", d[n - 1] + t);
      return 0;
    }
  }
  printf("Impossible");
  return 0;
}
