#include <bits/stdc++.h>
using namespace std;
template <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
int n, q;
class matris {
 public:
  bitset<151> m[151];
  void mul(matris x) {
    bitset<151> row[151], col[151];
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        if (m[i][j]) row[i][j] = 1;
        if (x.m[i][j]) col[j][i] = 1;
      }
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) m[i][j] = (row[i] & col[j]).any();
  }
} ans, cur;
matris Fe(matris x, int y) {
  if (y == 1) return x;
  matris h = Fe(x, y / 2);
  h.mul(h);
  if (y & 1) h.mul(x);
  return h;
}
int res = INT_MAX, vis[151];
vector<pair<int, int> > adj[151];
void bfs(int node, int cost) {
  memset(vis, 0, sizeof(vis));
  queue<pair<int, int> > q;
  q.push(make_pair(node, cost));
  while (!q.empty()) {
    int nd = q.front().first;
    int cs = q.front().second;
    q.pop();
    if (vis[nd]) continue;
    if (nd == n) {
      umin(res, cs);
      return;
    }
    vis[nd] = 1;
    for (typeof((adj[nd]).begin()) it = (adj[nd]).begin();
         it != (adj[nd]).end(); it++)
      if (cs >= it->second) q.push(make_pair(it->first, cs + 1));
  }
}
int main() {
  scanf("%d%d", &n, &q);
  vector<pair<int, pair<int, int> > > v;
  for (int i = 1; i <= q; i++) {
    int x, y, d;
    scanf("%d%d%d", &x, &y, &d);
    adj[x].push_back(make_pair(y, d));
    v.push_back(make_pair(d, make_pair(x, y)));
  }
  v.push_back(make_pair(0, make_pair(-1, -1)));
  sort(v.begin(), v.end());
  for (int i = 1; i <= n; i++) ans.m[i][i] = 1;
  for (int i = 1; i <= q; i++) {
    if (v[i].first > v[i - 1].first)
      ans.mul(Fe(cur, v[i].first - v[i - 1].first));
    for (int j = 1; j <= n; j++)
      if (ans.m[1][j]) bfs(j, v[i].first);
    cur.m[v[i].second.first][v[i].second.second] = 1;
  }
  if (res == INT_MAX)
    printf("Impossible\n");
  else
    printf("%d\n", res);
  return 0;
}
