#include<bits/stdc++.h>

using namespace std;

#define bt bitset<160>

const int inf = 0x3f3f3f3f;

int n,m,g[][];

bt ans[],a[],c[];

struct node {

    int x,y,z;

};

node d[];

inline bool cmp(const node x,const node y){return x.z<y.z;}

inline void mul(bt a[],bt b[]){

    int i,j,k;

    for(i=;i<=n;i++)c[i].reset();

    for(k=;k<=n;k++)

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

        if(a[i][k])c[i]|=b[k];

    for(i=;i<=n;i++)a[i]=c[i];

}

int main(){

    int i,j,k;

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

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

    sort(d+,d+m+,cmp);

    for(i=;i<=n;i++)ans[i].reset();

    for(i=;i<=n;i++)ans[i][i]=;

    int Ans=inf;

    for(int _=;_<=m;_++){

      for(i=;i<=n;i++)a[i].reset();

      for(i=;i<_;i++)a[d[i].x][d[i].y]=;

      k=d[_].z-d[_-].z;

      while(k){

          if(k&)mul(ans,a);

          mul(a,a);

          k>>=;

      }

      memset(g,0x3f,sizeof(g));

      for(i=;i<=n;i++)g[i][i]=;

      for(i=;i<=_;i++)g[d[i].x][d[i].y]=;

      for(k=;k<=n;k++)

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

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

            g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

      for(i=;i<=n;i++)if(ans[][i])Ans=min(Ans,d[_].z+g[i][n]);

    }

    if(Ans==inf)puts("Impossible");else printf("%d\n",Ans);

    return ;

}