#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:100000000")
using namespace std;
char v[151], vv[151], a[151][151];
unsigned long long a1[151][3], a2[151][3];
int m[151][151];
int n;
void sq() {
  int i, j, k;
  for (i = 0; i < n; i++)
    for (j = 0; j < 3; a1[i][j] = 0, a2[i][j] = 0, j++)
      ;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (a[i][j]) {
        a1[i][j >> 6] |= 1ull << (j & 63ull);
        a2[j][i >> 6] |= 1ull << (i & 63ull);
      }
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      for (a[i][j] = 0, k = 0; k < 3;
           a[i][j] |= (a1[i][k] & a2[j][k]) != 0, k++)
        ;
}
void mul() {
  int i, j;
  for (i = 0; i < n; i++)
    for (vv[i] = 0, j = 0; j < n; vv[i] |= a[j][i] & v[j], j++)
      ;
  for (i = 0; i < n; v[i] = vv[i], i++)
    ;
}
void pw(int p) {
  for (; p; sq(), p /= 2)
    if (p & 1) mul();
}
int t[151 * 151 * 5];
int main() {
  int k, i, j, c, l;
  scanf("%d%d", &n, &k);
  for (i = 0; i < n; i++)
    for (j = 0; j < n; m[i][j] = -1, j++)
      ;
  for (l = 0; l < k;
       scanf("%d%d%d", &i, &j, &c), t[l] = c, m[i - 1][j - 1] = c, l++)
    ;
  sort(t, t + k);
  k = unique(t, t + k) - t;
  v[0] = 1;
  c = 0;
  for (l = 0; l < k; l++) {
    if (t[l] > c) pw(t[l] - c);
    for (i = 0; i < n; i++)
      for (j = 0; j < n; j++)
        if (m[i][j] != -1 && m[i][j] <= t[l])
          a[i][j] = 1;
        else
          a[i][j] = 0;
    c = t[l];
    for (int z = 0; z < 151; mul(), c++, z++)
      if (v[n - 1])
        break;
      else if (l + 1 < k && t[l + 1] == c)
        break;
    if (v[n - 1]) break;
  }
  if (v[n - 1])
    printf("%d\n", c);
  else
    printf("Impossible\n");
  return 0;
}
