#include <bits/stdc++.h>
using namespace std;
const int N = 250;
const int ME = 151;
int dist[N];
int n, m;
int ans;
bool can[N], ncan[N];
vector<int> cur;
vector<pair<int, int> > g[N];
vector<int> gr;
struct Mat {
  int n;
  vector<bitset<ME> > a;
  Mat() { n = 0; }
  Mat(int Ne) {
    n = Ne;
    for (int i = 0; i < n; ++i) a.push_back(bitset<ME>(0));
  }
  void write() {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        cout << a[i][j] << " ";
      }
      cout << endl;
    }
  }
  Mat *transport() {
    Mat *tr = new Mat(n);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) tr->a[i][j] = a[j][i];
    return tr;
  }
  Mat *multiply(Mat *ar) {
    Mat *c = new Mat(n);
    Mat *tr = ar->transport();
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        int val = (a[i] & (tr->a[j])).count();
        if (val > 0) val = 1;
        c->a[i][j] = val;
      }
    }
    return c;
  }
};
Mat *M;
Mat *mPow(Mat *a, int n) {
  if (n == 1) return a;
  if (n % 2 == 0) {
    Mat *r = mPow(a, n / 2);
    r = r->multiply(r);
    return r;
  }
  Mat *r = a->multiply(mPow(a, n - 1));
  return r;
}
void try_bfs(int t) {
  vector<int> o;
  for (int i = 0; i < n; ++i) dist[i] = 1000000;
  for (int i = 0; i < n; ++i)
    if (can[i]) {
      o.push_back(i);
      dist[i] = 0;
    }
  int current = 0;
  while (current < (int)o.size()) {
    int v = o[current++];
    for (int i = 0; i < (int)g[v].size(); ++i) {
      if (g[v][i].first > t) break;
      int to = g[v][i].second;
      if (dist[to] > dist[v] + 1) {
        dist[to] = dist[v] + 1;
        o.push_back(to);
      }
    }
  }
  if (dist[n - 1] < n + 10) {
    if (ans == -1)
      ans = t + dist[n - 1];
    else
      ans = min(ans, t + dist[n - 1]);
  }
}
void buildMatrix(int t) {
  M = new Mat(n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < (int)g[i].size(); ++j) {
      if (g[i][j].first > t) break;
      M->a[i][g[i][j].second] = 1;
    }
  }
}
int main() {
  ans = -1;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    int u, v, t;
    scanf("%d%d%d", &u, &v, &t);
    u--;
    v--;
    g[u].push_back(make_pair(t, v));
    gr.push_back(t);
  }
  for (int i = 0; i < n; ++i) sort(g[i].begin(), g[i].end());
  gr.push_back(0);
  sort(gr.begin(), gr.end());
  vector<int> cur;
  for (int i = 0; i < (int)gr.size(); ++i) {
    if (i == 0 || gr[i] != gr[i - 1]) cur.push_back(gr[i]);
  }
  int last = 0;
  can[0] = true;
  try_bfs(0);
  for (int i = 1; i < (int)cur.size(); ++i) {
    buildMatrix(last);
    M = mPow(M, cur[i] - last);
    if (ans != -1 && cur[i] >= ans) break;
    for (int i = 0; i < n; ++i) ncan[i] = false;
    for (int qi = 0; qi < n; ++qi) {
      for (int qj = 0; qj < n; ++qj)
        if (M->a[qi][qj] && can[qi]) ncan[qj] = true;
    }
    for (int j = 0; j < n; ++j) {
      can[j] = ncan[j];
      ncan[j] = false;
    }
    try_bfs(cur[i]);
    last = cur[i];
  }
  if (ans == -1) {
    cout << "Impossible" << endl;
    return 0;
  }
  printf("%d\n", ans);
  return 0;
}
