#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const long long INF = 1LL << 50;
const int MAXN = 160;
int n, m;
struct edge {
  int u, v, d;
} e[MAXN];
bool cmp(edge a, edge b) { return a.d < b.d; }
struct Mx {
  bitset<MAXN> a[MAXN];
  void clear() {
    for (int i = 1; i <= n; ++i) a[i].reset();
  }
  void stand() {
    clear();
    for (int i = 1; i <= n; ++i) a[i][i] = 1;
  }
  Mx operator*(const Mx &b) {
    Mx c;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        if (a[i][j]) c.a[i] |= b.a[j];
    return c;
  }
} A, B;
Mx Mx_pow(Mx t, int v) {
  Mx res;
  res.stand();
  while (v) {
    if (v & 1) res = res * t;
    t = t * t;
    v >>= 1;
  }
  return res;
}
long long Floyd(Mx t) {
  long long dis[MAXN][MAXN];
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) dis[i][j] = (t.a[i][j]) ? 1 : INF;
  for (int i = 1; i <= n; ++i)
    if (A.a[1][i]) dis[i][i] = 0;
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        if (dis[i][k] < INF && dis[k][j] < INF)
          dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  long long ans = INF;
  for (int i = 1; i <= n; ++i)
    if (A.a[1][i]) ans = min(ans, dis[i][n]);
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].d);
  }
  sort(e + 1, e + m + 1, cmp);
  if (e[1].d > 0) {
    printf("Impossible\n");
    return 0;
  }
  int pos = 0;
  A.clear();
  B.clear();
  A.a[1][1] = 1;
  long long ans = INF;
  for (int i = 1; i <= m; ++i) {
    if (pos < e[i].d) {
      A = A * Mx_pow(B, e[i].d - pos);
      pos = e[i].d;
    }
    while (i <= m && e[i].d == pos) {
      int u = e[i].u;
      int v = e[i].v;
      B.a[u][v] = 1;
      ++i;
    }
    --i;
    ans = min(ans, (long long)pos + Floyd(B));
  }
  if (ans >= INF)
    printf("Impossible\n");
  else
    printf("%I64d\n", ans);
  return 0;
}
