#include <bits/stdc++.h>
using namespace std;
const long double pi = 3.1415926535897932384626433832795l;
template <typename T>
inline auto sqr(T x) -> decltype(x * x) {
  return x * x;
}
template <typename T1, typename T2>
inline bool umx(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T1, typename T2>
inline bool umn(T1& a, T2 b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
const int N = 150;
const int X = 1000000000;
const int inf = X + N + 10;
struct Input {
  int n, st, fn;
  int d[N][N];
  bool read() {
    int m;
    if (!(cin >> n >> m)) {
      return 0;
    }
    st = 0, fn = n - 1;
    for (int i = int(0); i < int(n); ++i) {
      for (int j = int(0); j < int(n); ++j) {
        d[i][j] = inf;
      }
    }
    for (int i = int(0); i < int(m); ++i) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      --x;
      --y;
      umn(d[x][y], z);
    }
    return 1;
  }
  void init(const Input& input) { *this = input; }
};
struct Data : Input {
  int ans;
  void write() {
    if (ans == inf) {
      puts("Impossible");
      return;
    }
    printf("%d\n", ans);
  }
  virtual void solve() {}
  virtual void clear() { *this = Data(); }
};
struct Solution : Data {
  static const int D = 64;
  static const int L = (N + D - 1) / D;
  bool can[N], can0[N];
  int l[N];
  uint64_t a[2][N][L];
  uint64_t b[N][L];
  uint64_t tmp1[N][L], tmp2[N][L];
  void solve() {
    vector<int> v;
    for (int i = int(0); i < int(n); ++i) {
      for (int j = int(0); j < int(n); ++j) {
        v.push_back(d[i][j]);
      }
    }
    v.push_back(0);
    v.push_back(inf);
    sort((v).begin(), (v).end());
    v.erase(unique((v).begin(), (v).end()), v.end());
    v.pop_back();
    memset(can, 0, sizeof can);
    can[st] = 1;
    ans = inf;
    for (int i = int(0); i < int(n); ++i) {
      ;
    }
    for (int t = int(0); t < int(((int)(v).size())); ++t) {
      for (int i = int(0); i < int(n); ++i) {
        l[i] = inf;
      }
      queue<int> q;
      for (int i = int(0); i < int(n); ++i) {
        if (can[i]) {
          q.push(i);
          l[i] = 0;
        }
      }
      while (((int)(q).size())) {
        int x = q.front();
        q.pop();
        for (int i = int(0); i < int(n); ++i) {
          if (d[x][i] <= v[t] && umn(l[i], l[x] + 1)) {
            q.push(i);
          }
        }
      }
      umn(ans, v[t] + l[fn]);
      ;
      ;
      if (t + 1 == ((int)(v).size())) {
        break;
      }
      memset(a, 0, sizeof a);
      for (int i = int(0); i < int(n); ++i) {
        for (int j = int(0); j < int(n); ++j) {
          if (d[i][j] <= v[t]) {
            a[0][i][j / D] |= 1ull << (j % D);
            a[1][j][i / D] |= 1ull << (i % D);
          }
        }
      }
      for (int i = int(0); i < int(n); ++i) {
        ;
      }
      memset(b, 0, sizeof b);
      for (int i = int(0); i < int(n); ++i) {
        b[i][i / D] |= 1ull << (i % D);
        b[i][i / D] |= 1ull << (i % D);
      }
      int pw = v[t + 1] - v[t];
      ;
      while (pw) {
        if (pw & 1) {
          memcpy(tmp1, b, sizeof b);
          memset(b, 0, sizeof b);
          for (int i = int(0); i < int(n); ++i) {
            for (int j = int(0); j < int(n); ++j) {
              for (int k = int(0); k < int((n + D - 1) / D); ++k) {
                if (tmp1[i][k] & a[1][j][k]) {
                  b[i][j / D] |= 1ull << (j % D);
                  break;
                }
              }
            }
          }
        }
        memcpy(tmp1, a[0], sizeof a[0]);
        memcpy(tmp2, a[1], sizeof a[1]);
        memset(a, 0, sizeof a);
        for (int i = int(0); i < int(n); ++i) {
          for (int j = int(0); j < int(n); ++j) {
            for (int k = int(0); k < int((n + D - 1) / D); ++k) {
              if (tmp1[i][k] & tmp2[j][k]) {
                a[0][i][j / D] |= 1ull << (j % D);
                a[1][j][i / D] |= 1ull << (i % D);
                break;
              }
            }
          }
        }
        pw /= 2;
      }
      for (int i = int(0); i < int(n); ++i) {
        ;
      }
      memcpy(can0, can, sizeof can);
      memset(can, 0, sizeof can);
      for (int i = int(0); i < int(n); ++i) {
        if (can0[i]) {
          for (int j = int(0); j < int(n); ++j) {
            if (b[i][j / D] & (1ull << (j % D))) {
              can[j] = 1;
            }
          }
        }
      }
    }
  }
  void clear() { *this = Solution(); }
};
Solution sol;
int main() {
  cout.setf(ios::showpoint | ios::fixed);
  cout.precision(20);
  sol.read();
  sol.solve();
  sol.write();
  return 0;
}
