#include <bits/stdc++.h>
using namespace std;
int a[200], b[200], c[200], d[200];
int cur[200][200], curRow[200], newRow[200];
int mat[200][200];
int n, m;
struct matrix {
  bitset<200> a[200];
};
matrix mul(matrix &x, matrix &y) {
  matrix ans;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (x.a[i][j]) ans.a[i] |= y.a[j];
  return ans;
}
void process(int steps) {
  matrix y, x;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (mat[i][j]) y.a[i].set(j);
  for (int i = 0; i < n; i++) x.a[i].set(i);
  while (steps > 0) {
    if (steps & 1) x = mul(x, y);
    y = mul(y, y);
    steps >>= 1;
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) mat[i][j] = x.a[i][j];
}
void printMat() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) printf("%d ", mat[i][j]);
    printf("\n");
  }
}
int main() {
  cin >> n >> m;
  vector<int> d;
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
    d.push_back(c[i]);
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) cur[i][j] = 0;
  d.push_back(0);
  sort(d.begin(), d.end());
  d.erase(unique(d.begin(), d.end()), d.end());
  for (int i = 0; i < n; i++) curRow[i] = 0;
  curRow[0] = 1;
  cur[n - 1][n - 1] = 1;
  for (int i = 0; i < d.size(); i++) {
    for (int j = 0; j < m; j++)
      if (c[j] == d[i]) {
        cur[a[j]][b[j]] = 1;
      }
    int goTill = i + 1 < d.size() ? d[i + 1] : d[i] + 200 * 200;
    int steps = goTill - d[i];
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++) mat[j][k] = cur[j][k];
    process(steps);
    for (int j = 0; j < n; j++) {
      newRow[j] = 0;
      for (int k = 0; k < n; k++) newRow[j] |= (curRow[k] & mat[k][j]);
    }
    if (newRow[n - 1] == 1) {
      int ans = (1 << 30), sub = (1 << 30), temp;
      while (sub) {
        temp = ans - sub;
        sub >>= 1;
        if (temp <= 0) continue;
        for (int j = 0; j < n; j++)
          for (int k = 0; k < n; k++) mat[j][k] = cur[j][k];
        process(temp);
        for (int j = 0; j < n; j++) {
          newRow[j] = 0;
          for (int k = 0; k < n; k++) newRow[j] |= (curRow[k] & mat[k][j]);
        }
        if (newRow[n - 1] == 1) {
          ans = temp;
        }
      }
      cout << d[i] + ans << endl;
      return 0;
    }
    for (int j = 0; j < n; j++) curRow[j] = newRow[j];
  }
  cout << "Impossible" << endl;
}
