#include <bits/stdc++.h>
using namespace std;
int n, m;
bitset<155> ans[155], a[155], b[155], c[155];
void print(bitset<155> a[]) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) cout << a[i][j] << " ";
    cout << endl;
  }
}
void init(bitset<155> a[]) {
  for (int i = 1; i <= n; i++) a[i].reset();
}
void mat_mul(bitset<155> a[], bitset<155> b[], bitset<155> c[]) {
  bitset<155> tmp[155], cc[155];
  for (int i = 1; i <= n; i++) {
    cc[i].reset();
    for (int j = 1; j <= n; j++) tmp[i][j] = b[j][i];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if ((a[i] & tmp[j]).any())
        cc[i][j] = 1;
      else
        cc[i][j] = 0;
    }
  }
  for (int i = 1; i <= n; i++) c[i] = cc[i];
}
void mat_pow(bitset<155> a[], int x) {
  bitset<155> aa[155];
  init(aa);
  for (int i = 1; i <= n; i++) {
    aa[i] = a[i];
  }
  while (x) {
    if (x & 1) mat_mul(ans, aa, ans);
    x >>= 1;
    mat_mul(aa, aa, aa);
  }
}
struct node {
  int u, v, w;
} p[155];
bool cmp(node p1, node p2) { return p1.w < p2.w; }
void build(int x, bitset<155> a[]) {
  init(a);
  for (int i = 1; i <= x; i++) a[p[i].u].set(p[i].v);
}
void test() {
  for (int i = 1; i <= m + 150; i++) {
    mat_mul(ans, a, ans);
    if (ans[1][n] == 1) {
      cout << p[m].w + i << endl;
      return;
    }
  }
  cout << "Impossible" << endl;
}
int main() {
  int l, r, mid;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &p[i].u, &p[i].v, &p[i].w);
  sort(p + 1, p + 1 + m, cmp);
  if (p[1].w != 0) {
    cout << "Impossible" << endl;
    return 0;
  }
  init(ans);
  ans[1][1] = 1;
  for (int i = 1; i <= m; i++) {
    int j = i + 1;
    while (j <= m && p[j].w == p[j - 1].w) j++;
    build(j - 1, a);
    if (j == m + 1) {
      test();
      return 0;
    }
    for (int j = 1; j <= n; j++) c[j] = ans[j];
    mat_pow(a, p[j].w - p[j - 1].w);
    if (ans[1][n] == 1) {
      l = 1, r = p[j].w - p[j - 1].w;
      int ret = 0;
      while (l <= r) {
        mid = (l + r) >> 1;
        for (int i = 1; i <= n; i++) ans[i] = c[i];
        mat_pow(a, mid);
        if (ans[1][n] == 1)
          r = mid - 1, ret = mid;
        else
          l = mid + 1;
      }
      cout << p[j - 1].w + l << endl;
      return 0;
    }
    i = j - 1;
  }
}
