#include <bits/stdc++.h>

#define N 160

#define inf 0x3f3f3f3f

#define maxn 1000000

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int n,m,ans=inf;

int dis[N][N], f[N][N];

int cnt;

bitset<N> can[N], now[N], tmp[N], base[N];

struct Node

{

	int x,y,d;

	void scan() { scanf("%d%d%d",&x,&y,&d); }

	friend bool operator < (const Node &a, const Node &b)

	{

		return a.d < b.d;

	}

}e[N];

void Mul(bitset<N>*a,bitset<N>*b)

{

	bitset<N>ret[N];

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

		for(int j=1;j<=n;++j) if(a[i][j]) ret[i]|=b[j];

	for(int i=1;i<=n;++i) a[i]=ret[i];

}

void Pow(bitset<N>*a,int b)

{

	bitset<N>ret[N];

	for(int i=1;i<=n;++i) ret[i][i]=1;

	for(;b;b>>=1)

	{

		if(b&1) Mul(ret, a);

		Mul(a,a);

	}

	for(int i=1;i<=n;++i) a[i]=ret[i];

}

int main()

{

	// setIO("input");

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

	for(int i=1;i<=m;++i) e[i].scan();

	sort(e+1,e+1+m);

    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dis[i][j]=inf;

    for(int i=1;i<=n;++i) dis[i][i]=0;

    cnt=0,ans=inf;

    for(int i=1;i<=n;++i) can[i][i]=1;

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

    {

    	int x=e[i].x,y=e[i].y,d=e[i].d;

    	for(int j=1;j<=n;++j) tmp[j]=base[j];

    	Pow(tmp, d-cnt);

        Mul(can,tmp);

        for(int j=1;j<=n;++j) for(int k=1;k<=n;++k) dis[j][k]=min(dis[j][k], dis[j][x]+1+dis[y][k]);

        for(int j=1;j<=n-1;++j) if(can[1][j]) ans=min(ans, d + dis[j][n]);

        cnt=d;

        base[x][y]=1;

    }

    if(ans<0x3f3f3f3f) printf("%d\n",ans);

    else printf("Impossible\n");

	return 0;

}