#include <iostream>
#include <fstream>
#include <sstream>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>

#include <algorithm>
#include <numeric>

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

#define pb push_back
#define pbk pop_back
#define mp make_pair
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define len(a) ((int) (a).size())

#ifdef CUTEBMAING
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

using namespace std;

typedef long long int64;
typedef long double ld;
typedef unsigned long long lint;

const int inf = (1 << 30) - 1;
const int64 linf = (1ll << 62) - 1;
const int N = 160;
const int K = 30;

struct edges {
    int u, v;
};

int n, m;
map<int, vector<edges>> g;
vector<pair<int, vector<edges>>> events;

bitset<N> mat[K][N];

bitset<N> temp[N];

void mul(bitset<N> a[N], bitset<N> b[N], bitset<N> c[N]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            temp[j].set(i, b[i].test(j));
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            c[i].set(j, (a[i] & temp[j]).any());
        }
    }
}

int dist[N][N];
bool cur[N], ncur[N];

void apply(bitset<N> a[N]) {
    fill_n(ncur, n, 0);
    for (int i = 0; i < n; i++) {
        if (cur[i]) {
            for (int j = 0; j < n; j++) {
                if (a[i].test(j)) {
                    ncur[j] = true;
                }
            }
        }
    }
    memcpy(cur, ncur, sizeof(bool) * n);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, d; cin >> a >> b >> d;
        g[d].pb({a - 1, b - 1});
    }
    g[0].pb({n - 1, n - 1});
    g[inf].pb({n - 1, n - 1});
    events = vector<pair<int, vector<edges>>>(all(g));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = inf;
        }
        dist[i][i] = 0;
        mat[0][i].reset();
    }
    cur[0] = 1;
    int ans = inf;
    for (int i = 0; i < len(events) - 1; i++) {
        int curTime = events[i].fs, nextTime = events[i + 1].fs;
        for (edges e : events[i].sc) {
            mat[0][e.u].set(e.v, true);
            for (int j = 0; j < n; j++) {
                for (int z = 0; z < n; z++) {
                    dist[j][z] = min(dist[j][z], dist[j][e.u] + dist[e.v][z] + 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (cur[i]) {
                ans = min(ans, curTime + dist[i][n - 1]);
            }
        }
        for (int j = 1; j < K; j++) {
            mul(mat[j - 1], mat[j - 1], mat[j]);
        }
        int delta = nextTime - curTime;
        for (int j = K - 1; j >= 0; j--) {
            if (delta >= (1 << j)) {
                apply(mat[j]);
                delta -= (1 << j);
            }
        }
    }
    if (ans >= inf) {
        cout << "Impossible" << endl;
    } else {
        cout << ans << endl;
        eprintf("ans = %d\n", ans);
    }
    return 0;
}