#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<bitset>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn=, inf=1e9+;

struct mtx{bitset<maxn>mp[maxn]; mtx(){for(int i=;i<maxn;i++) mp[i].reset();}}tmp, tmp2, f, base, h[];

struct poi{int x, y, dis;}a[maxn];

int n, m;

mtx operator *(mtx a, mtx b)

{

    mtx c;

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

    if(a.mp[i][j]) c.mp[i]|=b.mp[j];

    return c;

}

mtx operator |(mtx a, mtx b)

{

    mtx c;

    for(int i=;i<=n;i++)

    c.mp[i]|=a.mp[i]|b.mp[i];

    return c;

}

inline void power(int b)

{

    if(b<=) return;

    for(;b;b>>=, tmp=tmp*tmp)

    if(b&) f=f*tmp;

}

inline bool cmp(poi a, poi b){return a.dis<b.dis;}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i=;i<=m;i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].dis);

    sort(a+, a++m, cmp); a[m+].dis=inf;

    if(a[].dis) return puts("Impossible"), ;

    for(int i=;i<=n;i++) f.mp[i][i]=;

    for(int i=;i<=m;i++)

    {

        tmp=base; power(a[i].dis-a[i-].dis);

        base.mp[a[i].x][a[i].y]=;

        int up=log2(a[i+].dis-a[i].dis);

        h[]=base; for(int j=;j<=n;j++) h[].mp[j][j]=h[].mp[j][j]|;

        mtx tmpx; for(int j=;j<=n;j++) tmpx.mp[j][j]=;

        if(a[i+].dis-a[i].dis & ) tmpx=tmpx|(tmpx*h[]);

        for(int j=;j<=up;j++)

        {

            h[j]=h[j-]*h[j-];

            if(a[i+].dis-a[i].dis & (<<j)) tmpx=tmpx|(tmpx*h[j]);

        }

        tmpx=f*tmpx;

        if(!tmpx.mp[][n]) continue;

        mtx tmp1=f; int ans=;

        for(int j=up;j>=;j--)

        if(a[i].dis+ans+(<<j)<=a[i+].dis)

        {

            tmp2=tmp1; tmp2=tmp2*h[j];

            if(tmp2.mp[][n]) continue;

            ans+=(<<j); tmp1=tmp2;

        }

        return printf("%d\n", a[i].dis+ans+), ;

    }

    puts("Impossible");

}