#include <bits/stdc++.h>
using namespace std;
const int N = 155;
int n, m, ans = 0x3f3f3f3f;
int dis[N][N];
struct Eg {
  int u, v, w;
} eg[N];
bitset<N> res[N], e[N], z[N];
bool cmp(Eg x, Eg y) { return x.w < y.w; }
void mul(bitset<N> x[N], bitset<N> y[N]) {
  for (int i = (1); i <= (n); ++i) z[i].reset();
  for (int k = (1); k <= (n); ++k)
    for (int i = (1); i <= (n); ++i)
      if (x[i][k]) z[i] |= y[k];
  for (int i = (1); i <= (n); ++i) x[i] = z[i];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (m); ++i)
    scanf("%d%d%d", &eg[i].u, &eg[i].v, &eg[i].w);
  sort(eg + 1, eg + m + 1, cmp);
  for (int i = (1); i <= (n); ++i) res[i].reset();
  for (int i = (1); i <= (n); ++i) res[i][i] = 1;
  for (int k = (1); k <= (m); ++k) {
    for (int i = (1); i <= (n); ++i) e[i].reset();
    memset(dis, 63, sizeof(dis));
    for (int i = (1); i <= (k - 1); ++i) e[eg[i].u][eg[i].v] = 1;
    int t = eg[k].w - eg[k - 1].w;
    while (t) {
      if (t & 1) mul(res, e);
      mul(e, e), t >>= 1;
    }
    for (int i = (1); i <= (n); ++i) dis[i][i] = 0;
    for (int i = (1); i <= (k); ++i) dis[eg[i].u][eg[i].v] = 1;
    for (int l = (1); l <= (n); ++l)
      for (int i = (1); i <= (n); ++i)
        for (int j = (1); j <= (n); ++j)
          dis[i][j] = min(dis[i][j], dis[i][l] + dis[l][j]);
    for (int i = (1); i <= (n); ++i)
      if (res[1][i]) ans = min(ans, eg[k].w + dis[i][n]);
  }
  if (ans == 0x3f3f3f3f)
    puts("Impossible");
  else
    printf("%d\n", ans);
  return 0;
}
