#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<tuple<int, int, int>> edge;
vector<int> g[150];
bitset<150> vis, nw_vis;
int dist[150];
struct ej {
  bitset<150> adj[150];
  bitset<150> radj[150];
  ej() {
    for (int i = 0; i < 150; i++) {
      adj[i].reset();
      radj[i].reset();
    }
  }
  ej operator*(const ej &p) {
    ej M;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        M.adj[i][j] = ((adj[i] & p.radj[j]).count() > 0);
        M.radj[j][i] = M.adj[i][j];
      }
    }
    return M;
  }
} base;
int bfs() {
  for (int i = 0; i < n; i++) dist[i] = 1e5;
  queue<int> que;
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      que.push(i);
      dist[i] = 0;
    }
  }
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int v : g[u]) {
      if (dist[v] > dist[u] + 1) {
        dist[v] = dist[u] + 1;
        que.push(v);
      }
    }
  }
  if (dist[n - 1] == 1e5) return -1;
  return dist[n - 1];
}
ej multiply(int pow) {
  if (pow == 1) return base;
  if (pow & 1) {
    return base * multiply(pow - 1);
  } else {
    ej t = multiply(pow / 2);
    return t * t;
  }
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    edge.push_back(make_tuple(w, u, v));
  }
  sort(edge.begin(), edge.end());
  if (get<0>(edge[0]) != 0) {
    cout << "Impossible" << endl;
    return 0;
  }
  int cur = 0;
  vis[0] = 1;
  int ans = 2e9;
  for (int i = 0, j = 0; i < m;) {
    int cur = get<0>(edge[i]);
    while (j < m && get<0>(edge[j]) == get<0>(edge[i])) {
      int u = get<1>(edge[j]), v = get<2>(edge[j]), w = get<0>(edge[j]);
      base.adj[v][u] = 1;
      base.radj[u][v] = 1;
      g[u].push_back(v);
      j++;
    }
    int dist = bfs();
    if (dist != -1) {
      ans = min(ans, dist + cur);
    }
    int d;
    if (j != m) {
      d = get<0>(edge[j]) - get<0>(edge[i]);
      ej M = multiply(d);
      for (int k = 0; k < n; k++) {
        nw_vis[k] = (M.adj[k] & vis).count() > 0;
      }
      vis = nw_vis;
    }
    i = j;
  }
  if (ans != 2e9) {
    cout << ans << endl;
  } else {
    cout << "Impossible" << endl;
  }
}
