#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000002;
const long long INFLL = 100000000000000000ll;
const long long MOD = 1000000007;
struct Matrix {
  struct Array {
    vector<int> p;
    int sz;
    int getSize() { return sz; }
    Array(int _sz) {
      p.resize(_sz, 0);
      sz = _sz;
    }
    int& operator[](int idx) { return p[idx]; }
  };
  int sz;
  vector<Array> v;
  Matrix(int p1, int p2) {
    sz = p1;
    v.resize(p1, Array(p2));
  }
  int getSize() { return sz; }
  Array& operator[](int idx) { return v[idx]; }
};
Matrix mult(Matrix m1, Matrix m2) {
  int n = m1.getSize();
  bitset<150> temp;
  bitset<150> row[n], col[n];
  for (int i = (0); i <= (n - 1); i++)
    for (int j = (0); j <= (n - 1); j++)
      col[j][i] = m2[i][j], row[i][j] = m1[i][j];
  Matrix ret(n, n);
  for (int i = (0); i <= (n - 1); i++)
    for (int j = (0); j <= (n - 1); j++) {
      temp = row[i] & col[j];
      ret[i][j] = temp.count() > 0;
    }
  return ret;
}
Matrix pow(Matrix m, long long e) {
  int n = m.getSize();
  Matrix ret(n, n);
  for (int i = (0); i <= (n - 1); i++) ret[i][i] = 1;
  while (e) {
    if (e & 1) ret = mult(ret, m);
    m = mult(m, m);
    e /= 2;
  }
  return ret;
}
long long D[155][155], N, E;
set<pair<int, pair<int, int>>> F;
int main() {
  cin >> N >> E;
  Matrix m(N, N);
  for (int i = (0); i <= (N - 1); i++)
    for (int j = (0); j <= (N - 1); j++) D[i][j] = INFLL;
  for (int i = (0); i <= (N - 1); i++) D[i][i] = 0;
  vector<int> can(N, 0), can2(N, 0), pend[N];
  can[0] = 1;
  for (int e = (1); e <= (E); e++) {
    int a, b, d;
    cin >> a >> b >> d;
    if (d > 0)
      F.insert({d, {a - 1, b - 1}});
    else {
      m[a - 1][b - 1] = 1;
      for (int i = (0); i <= (N - 1); i++)
        for (int j = (0); j <= (N - 1); j++)
          D[i][j] = min(D[i][j], D[i][a - 1] + D[b - 1][j] + 1);
    }
  }
  long long ans = INFLL, last = 0;
  for (int i = (0); i <= (N - 1); i++)
    if (can[i]) ans = min(ans, D[i][N - 1]);
  for (auto it = F.begin(); it != F.end(); it++) {
    int d = it->first;
    int a = it->second.first, b = it->second.second;
    Matrix adj = pow(m, d - last);
    last = d;
    for (int i = (0); i <= (N - 1); i++) can2[i] = 0;
    for (int i = (0); i <= (N - 1); i++)
      for (int j = (0); j <= (N - 1); j++) can2[j] |= can[i] & adj[i][j];
    for (int i = (0); i <= (N - 1); i++) can[i] = can2[i];
    m[a][b] = 1;
    long long need = INFLL;
    for (int i = (0); i <= (N - 1); i++)
      if (can[i]) need = min(need, D[i][a]);
    if (need == 0) {
      for (int i = (0); i <= (N - 1); i++)
        for (int j = (0); j <= (N - 1); j++)
          D[i][j] = min(D[i][j], D[i][a] + D[b][j] + 1);
      m[a][b] = 1;
      queue<int> q;
      q.push(b);
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : pend[u]) {
          m[u][v] = 1, q.push(v);
          for (int i = (0); i <= (N - 1); i++)
            for (int j = (0); j <= (N - 1); j++)
              D[i][j] = min(D[i][j], D[i][u] + D[v][j] + 1);
        }
        pend[u].clear();
      }
    } else if (need < INFLL)
      F.insert({d + need, {a, b}});
    else
      pend[a].push_back(b);
    for (int i = (0); i <= (N - 1); i++)
      if (can[i]) ans = min(ans, d + D[i][N - 1]);
  }
  if (ans < INFLL)
    cout << ans;
  else
    cout << "Impossible";
}
