#include <bits/stdc++.h>
using namespace std;
vector<int> vec[155];
bitset<155> bt[155], bt2[155];
struct node {
  int x, y, ds;
} ar[155];
bool comp(node a, node b) { return a.ds < b.ds; }
queue<int> q;
bool cnt[155], d[155][155], e[155][155], tmp[155][155], cnt2[155];
int n, m, i, j, k, a, b, c, dist[155], son, t;
void mrg() {
  int i, j, k;
  bool tmp[155][155];
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
      bt[i][j] = d[i][j];
      bt2[i][j] = d[j][i];
    }
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      tmp[i][j] = (bt[i] & bt2[j]).any();
    }
  }
  memcpy(d, tmp, sizeof tmp);
}
void crp() {
  int i, j, k;
  bool tmp[155][155];
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
      bt[i][j] = d[i][j];
      bt2[i][j] = e[j][i];
    }
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      tmp[i][j] = (bt[i] & bt2[j]).any();
    }
  }
  memcpy(d, tmp, sizeof tmp);
}
void carp(int x) {
  if (x == 1) return;
  carp(x / 2);
  mrg();
  if (x % 2) crp();
}
int main() {
  scanf("%d %d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%d %d %d", &a, &b, &c);
    a--;
    b--;
    ar[i].x = a;
    ar[i].y = b;
    ar[i].ds = c;
  }
  sort(ar + 1, ar + m + 1, comp);
  cnt[0] = 1;
  if (ar[1].ds) {
    printf("Impossible\n");
    return 0;
  }
  for (t = 1; t <= m; t++) {
    int val = ar[t].ds;
    int diff = val - son;
    son = val;
    if (diff) {
      memcpy(d, tmp, sizeof tmp);
      memcpy(e, d, sizeof d);
      carp(diff);
      for (i = 0; i < n; i++) {
        bool res = 0;
        for (j = 0; j < n; j++) {
          res = cnt[j] & d[j][i];
          if (res) break;
        }
        cnt2[i] = res;
      }
      for (i = 0; i < n; i++) cnt[i] = cnt2[i];
    }
    tmp[ar[t].x][ar[t].y] = 1;
    vec[ar[t].x].push_back(ar[t].y);
    while (!q.empty()) q.pop();
    for (i = 0; i < n; i++) {
      dist[i] = 2 * 1e9;
      if (cnt[i]) {
        dist[i] = son;
        q.push(i);
        if (i == n - 1) {
          printf("%d\n", son);
          return 0;
        }
      }
    }
    while (!q.empty()) {
      int fr = q.front();
      if (fr == n - 1) {
        printf("%d\n", dist[fr]);
        return 0;
      }
      q.pop();
      for (i = 0; i < vec[fr].size(); i++) {
        int nd = vec[fr][i];
        if (dist[nd] > dist[fr] + 1) {
          q.push(nd);
          dist[nd] = dist[fr] + 1;
        }
      }
    }
  }
  printf("Impossible\n");
  return 0;
}
