#include <bits/stdc++.h>
using namespace std;
const long long inf = 2e18 + 7;
const long long mod = 1e9 + 7;
const double eps = 1e-12;
const double PI = 2 * acos(0.0);
const double E = 2.71828;
int n, m;
map<int, vector<pair<int, int>>> g;
vector<pair<int, int>> edges;
struct Matrix {
  bitset<155> mt[155];
  Matrix() {}
  void setOne(int x, int y) { mt[x][y] = 1; }
};
Matrix operator*(Matrix a, Matrix b) {
  Matrix res;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (a.mt[i][j]) res.mt[i] |= b.mt[j];
    }
  }
  return res;
}
Matrix Pow(Matrix a, int N) {
  Matrix res;
  for (int i = 0; i < n; ++i) {
    res.setOne(i, i);
  }
  while (N) {
    if (N & 1) {
      res = res * a;
    }
    a = a * a;
    N /= 2;
  }
  return res;
}
Matrix p, moves;
bool used[155];
int dist[155];
int findWay() {
  for (int i = 0; i < n; ++i) {
    dist[i] = 2 * mod;
    used[i] = false;
    if (p.mt[0][i]) {
      dist[i] = 0;
    }
  }
  for (int i = 0; i < n; ++i) {
    int v = -1;
    for (int j = 0; j < n; ++j) {
      if (!used[j] && (v == -1 || dist[j] < dist[v])) {
        v = j;
      }
    }
    if (v == -1 || dist[v] == 2 * mod) {
      break;
    }
    used[v] = true;
    for (int j = 0; j < n; ++j) {
      if (moves.mt[v][j] == 1 && dist[j] > dist[v] + 1) {
        dist[j] = dist[v] + 1;
      }
    }
  }
  return dist[n - 1];
}
int main(void) {
  scanf("%d %d", &n, &m);
  vector<int> cmp;
  for (int i = 0; i < m; ++i) {
    int a, b, d;
    scanf("%d %d %d", &a, &b, &d);
    --a;
    --b;
    g[d].push_back({a, b});
    cmp.push_back(d);
  }
  sort((cmp).begin(), (cmp).end());
  cmp.erase(unique((cmp).begin(), (cmp).end()), cmp.end());
  int last = 0, res = 2 * mod;
  p.setOne(0, 0);
  for (int i = 0; i < cmp.size(); ++i) {
    int diff = cmp[i] - last;
    p = p * Pow(moves, diff);
    vector<pair<int, int>> x = g[cmp[i]];
    for (int j = 0; j < x.size(); ++j) {
      moves.setOne(x[j].first, x[j].second);
    }
    int value = findWay();
    if (value != 2 * mod) {
      res = min(res, last + diff + value);
    }
    last += diff;
  }
  if (res == 2 * mod) {
    puts("Impossible");
  } else {
    printf("%d\n", res);
  }
  return 0;
}
