#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 150 + 2;
const long long INF = 1e13;
class Mat {
 public:
  bitset<MAXN> bs[MAXN], bsrev[MAXN];
};
long long n, m;
vector<pair<long long, pair<long long, long long> > > e;
Mat mat0, mat;
bool ar[MAXN];
bool tmp[MAXN];
long long dist[MAXN];
Mat zarb(Mat a, Mat b) {
  Mat ret;
  for (long long i = 0; i < MAXN; i++)
    for (long long j = 0; j < MAXN; j++)
      ret.bs[i][j] = ret.bsrev[j][i] = (a.bs[i] & b.bsrev[j]).any();
  return ret;
}
Mat tavan(Mat a, long long p) {
  Mat ret;
  if (p == 0) return mat0;
  ret = tavan(a, p / 2);
  ret = zarb(ret, ret);
  if (p % 2 == 0) return ret;
  return ret = zarb(ret, a);
}
void setMat0() {
  for (long long i = 0; i < MAXN; i++) mat0.bs[i][i] = mat0.bsrev[i][i] = true;
}
void inp() {
  cin >> n >> m;
  for (long long i = 0; i < m; i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    e.push_back({w, {--u, --v}});
  }
}
void ms_bfs() {
  queue<long long> q;
  for (long long i = 0; i < n; i++) {
    dist[i] = (ar[i] ? 0 : INF);
    if (!dist[i]) q.push(i);
  }
  while (!q.empty()) {
    long long v = q.front();
    q.pop();
    for (long long u = 0; u < n; u++)
      if (mat.bs[v][u] && dist[u] > dist[v] + 1)
        dist[u] = dist[v] + 1, q.push(u);
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  inp();
  sort(e.begin(), e.end());
  setMat0();
  ar[0] = 1;
  long long ans = INF;
  for (long long i = 0; i < m; i++) {
    long long u = e[i].second.first, v = e[i].second.second;
    Mat now;
    if (!i)
      now = tavan(mat, e[i].first);
    else
      now = tavan(mat, e[i].first - e[i - 1].first);
    mat.bs[u][v] = mat.bsrev[v][u] = true;
    memset(tmp, 0, sizeof tmp);
    for (long long j = 0; j < n; j++)
      for (long long k = 0; k < n; k++) {
        if (ar[k] && now.bs[k][j]) tmp[j] = true;
      }
    for (long long j = 0; j < n; j++) ar[j] = tmp[j];
    ms_bfs();
    if (dist[n - 1] != INF) ans = min(ans, e[i].first + dist[n - 1]);
  }
  if (ans == INF) return cout << "Impossible" << '\n', 0;
  return cout << ans << '\n', 0;
}
