#include <bits/stdc++.h>
using namespace std;
const int MAX = 159, INF = 2e9 + 9;
struct mat {
  bitset<MAX> a[MAX];
  mat(int v = 0) {
    for (int i = 0; i < MAX; i++)
      for (int j = 0; j < MAX; j++)
        if (i == j)
          a[i][j] = v;
        else
          a[i][j] = 0;
  }
} adj(0);
mat operator*(mat a, mat b) {
  mat tmp(0), ret(0);
  for (int i = 0; i < MAX; i++)
    for (int j = 0; j < MAX; j++) tmp.a[i][j] = b.a[j][i];
  for (int i = 0; i < MAX; i++)
    for (int j = 0; j < MAX; j++)
      ret.a[i][j] = ((a.a[i] & tmp.a[j]).count() > 0);
  return ret;
}
mat operator^(mat a, int n) {
  mat ret(1);
  if (!n) return ret;
  ret = a ^ (n >> 1);
  if (n & 1) return ret * ret * a;
  return ret * ret;
}
map<int, vector<pair<int, int> > > m;
bitset<MAX> can, t;
bool mark[MAX];
vector<int> g[MAX];
long long n, e, a, b, d, dis[MAX][MAX], h[MAX];
queue<int> q;
long long bfs() {
  while (q.size()) {
    int v = q.front();
    q.pop();
    if (v == n - 1) return h[v];
    for (auto u : g[v])
      if (!mark[u]) q.push(u), h[u] = h[v] + 1, mark[u] = true;
  }
  return INF;
}
int main() {
  cin >> n >> e;
  for (int i = 0; i < MAX; i++)
    for (int j = 0; j < MAX; j++) dis[i][j] = (i == j ? 0 : INF);
  for (int i = 0; i < e; i++)
    cin >> a >> b >> d, a--, b--, m[d].push_back({a, b}), dis[a][b] = 1;
  can[0] = 1, m[0].push_back({0, 0}), m[0].pop_back();
  long long last, ans = INF;
  for (map<int, vector<pair<int, int> > >::iterator it = m.begin();
       it != m.end(); it++) {
    long long d1 = it->first;
    it++;
    if (it == m.end()) {
      it--;
      last = it->first;
      break;
    }
    long long d2 = it->first;
    it--;
    for (auto i : it->second)
      adj.a[i.first][i.second] = 1, g[i.first].push_back(i.second);
    memset(h, 0, sizeof h), memset(mark, 0, sizeof mark);
    while (q.size()) q.pop();
    for (int i = 0; i < MAX; i++)
      if (can[i]) mark[i] = true, q.push(i);
    ans = min(ans, bfs() + d1);
    mat tmp = adj, tmp2;
    tmp = tmp ^ (d2 - d1);
    for (int i = 0; i < MAX; i++)
      for (int j = 0; j < MAX; j++) tmp2.a[i][j] = tmp.a[j][i];
    t = can;
    for (int i = 0; i < MAX; i++) can[i] = (t & tmp2.a[i]).count() > 0;
  }
  for (int k = 0; k < MAX; k++)
    for (int i = 0; i < MAX; i++)
      for (int j = 0; j < MAX; j++)
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  for (int i = 0; i < MAX; i++)
    if (can[i]) ans = min(ans, dis[i][n - 1] + last);
  if (ans < INF)
    cout << ans;
  else
    cout << "Impossible";
}
