#include <bits/stdc++.h>
using namespace std;
template <class T>
T sqr(const T &a) {
  return a * a;
}
const int MAXN = 155, INF = 2e9;
bitset<MAXN> res[MAXN], tmp[MAXN], a[MAXN], b[MAXN];
int n, used[MAXN], d[MAXN], q[MAXN * MAXN], head, tail, m, x, y, z;
map<int, vector<pair<int, int> > > Map;
int bfs(int v) {
  used[v] = 1;
  for (int i = 0; i < (int)n; i++) d[i] = INF;
  d[v] = 0;
  head = tail = 0;
  q[head++] = v;
  while (head > tail) {
    int v = q[tail++];
    for (int i = 0; i < (int)n; i++) {
      if (a[i][v] && d[i] == INF) {
        d[i] = d[v] + 1;
        q[head++] = i;
        if (i == n - 1) return d[i];
      }
    }
  }
  return INF;
}
void mult(bitset<MAXN> *arow, bitset<MAXN> *bcol) {
  bitset<MAXN> c[MAXN];
  for (int i = 0; i < (int)n; i++)
    for (int j = 0; j < (int)n; j++) {
      c[i][j] = (arow[i] & bcol[j]).count() > 0;
    }
  for (int i = 0; i < (int)n; i++) arow[i] = c[i];
}
void fastpow(int p) {
  if (!p) return;
  fastpow(p / 2);
  for (int i = 0; i < (int)n; i++)
    for (int j = 0; j < (int)n; j++) tmp[i][j] = res[j][i];
  mult(res, tmp);
  if (p % 2 == 1) mult(res, a);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < (int)m; i++) {
    scanf("%d%d%d", &x, &y, &z);
    x--, y--;
    Map[z].push_back(make_pair(x, y));
  }
  b[0][0] = 1;
  int ans = INF;
  for (auto it = Map.begin(); it != Map.end(); it++) {
    if (it == Map.begin() && it->first > 0) break;
    auto &edges = it->second;
    for (int i = 0; i < (int)(int)edges.size(); i++)
      a[edges[i].second][edges[i].first] = 1;
    for (int i = 0; i < (int)n; i++) {
      if (b[0][i]) {
        int tmp = bfs(i);
        if (tmp < INF) ans = min(ans, tmp + it->first);
      }
    }
    auto nextIt = it;
    nextIt++;
    if (nextIt == Map.end()) break;
    for (int i = 0; i < (int)n; i++)
      for (int j = 0; j < (int)n; j++) res[i][j] = 0;
    for (int i = 0; i < (int)n; i++) res[i][i] = 1;
    int delta = nextIt->first - it->first;
    fastpow(delta);
    for (int i = 0; i < (int)n; i++)
      for (int j = 0; j < (int)n; j++) tmp[i][j] = res[j][i];
    mult(b, tmp);
  }
  if (ans == INF)
    puts("Impossible");
  else
    printf("%d\n", ans);
}
