#include <bits/stdc++.h>
using namespace std;
int N, M;
int A[200], B[200], D[200];
map<int, vector<int>> MM;
set<int> S;
struct mat {
  signed long long v[150][3] = {};
};
struct vec {
  signed long long v[3] = {};
};
void print(mat a, int n) {
  int x, y;
  for (x = 0; x < n; x++) {
    (void)printf("%d: ", x);
    for (y = 0; y < n; y++)
      (void)printf("%d", (a.v[x][y / 64] & (1LL << (y % 64))) != 0);
    (void)printf("\n");
  }
}
void print(vec a, int n) {
  int i;
  for (i = 0; i < n; i++)
    (void)printf("%d", (a.v[i / 64] & (1LL << (i % 64))) != 0);
  (void)printf("\n");
}
mat mult(mat a, mat b, int n) {
  mat c, d;
  int x, y, z;
  for (x = 0; x < n; x++)
    for (y = 0; y < n; y++)
      if (b.v[y][x / 64] & (1LL << (x % 64))) c.v[x][y / 64] |= 1LL << (y % 64);
  for (x = 0; x < n; x++)
    for (y = 0; y < n; y++) {
      signed long long v = 0;
      for (z = 0; z < (n + 63) / 64; z++) v |= a.v[x][z] & c.v[y][z];
      v = (v != 0);
      d.v[x][y / 64] |= v << (y % 64);
    }
  return d;
}
mat init(int n) {
  mat r;
  int x;
  for (x = 0; x < n; x++) r.v[x][x / 64] |= 1LL << (x % 64);
  return r;
}
mat powm(mat a, int p, int n) {
  mat r = init(n);
  while (p) {
    if (p % 2) r = mult(r, a, n);
    a = mult(a, a, n);
    p /= 2;
  }
  return r;
}
vec mult(mat a, vec b, int n) {
  vec c;
  int x, y;
  for (x = 0; x < n; x++)
    if (b.v[x / 64] & (1LL << (x % 64)))
      for (y = 0; y < (n + 63) / 64; y++) c.v[y] |= a.v[x][y];
  return c;
}
bool reachable(mat a, vec b) {
  int x, y;
  for (x = 0; x < 150; x++) {
    vec c = mult(a, b, N);
    b.v[0] |= c.v[0];
    b.v[1] |= c.v[1];
    b.v[2] |= c.v[2];
  }
  int n = N - 1;
  return (b.v[n / 64] & (1LL << (n % 64))) != 0;
}
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N >> M;
  for (i = 0; i < M; i++) {
    cin >> A[i] >> B[i] >> D[i];
    A[i]--;
    B[i]--;
    MM[D[i]].push_back(i);
    S.insert(D[i]);
  }
  int cur = 0;
  vec v;
  mat m;
  v.v[0] = 1;
  for (auto& r : MM) {
    v = mult(powm(m, r.first - cur, N), v, N);
    cur = r.first;
    for (auto& r2 : r.second) m.v[A[r2]][B[r2] / 64] |= 1LL << (B[r2] % 64);
    if (reachable(m, v)) break;
  }
  if (!reachable(m, v)) return (void)printf("Impossible\n");
  int n = N - 1;
  while ((v.v[n / 64] & (1LL << (n % 64))) == 0) {
    v = mult(m, v, N);
    cur++;
    if (S.count(cur))
      for (auto& r2 : MM[cur]) m.v[A[r2]][B[r2] / 64] |= 1LL << (B[r2] % 64);
  }
  cout << cur << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false);
  for (i = 0; i < argc - 1; i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < s.size(); i++) ungetc(s[s.size() - 1 - i], stdin);
  solve();
  return 0;
}
