#include<iostream> #include<cstdio> #include<queue> using namespace std; struct edge{ int to,next,v; }e[200001]; int n,r,cnt,head[5001]; bool inq[5001]; long long dis[5001],dis2[5001]; queue<int> q; void insert(int u,int v,int w){ e[++cnt]=(edge){v,head[u],w}; head[u]=cnt; } void spfa(){ for(int i=1;i<=n;i++) dis[i]=dis2[i]=1e15; int now,i; q.push(1);inq[1]=1;dis[1]=0; while(!q.empty()){ now=q.front();q.pop(); i=head[now]; while(i){ if(dis[now]+e[i].v<dis[e[i].to]){ dis2[e[i].to]=dis[e[i].to]; dis[e[i].to]=dis[now]+e[i].v; if(!inq[e[i].to]){ inq[e[i].to]=1; q.push(e[i].to); } } else if(dis[now]+e[i].v<dis2[e[i].to]&&dis[now]+e[i].v>dis[e[i].to]){ dis2[e[i].to]=dis[now]+e[i].v; if(!inq[e[i].to]){ inq[e[i].to]=1; q.push(e[i].to); } } if(dis2[now]+e[i].v<dis2[e[i].to]){ dis2[e[i].to]=dis2[now]+e[i].v; if(!inq[e[i].to]){ inq[e[i].to]=1; q.push(e[i].to); } } i=e[i].next; } inq[now]=0; } if(dis2[n]!=1e15)printf("%d",dis2[n]); else printf("-1"); } inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main(){ n=read();r=read(); for(int i=1;i<=r;i++){ int a=read(),b=read(),d=read(); insert(a,b,d);insert(b,a,d); } spfa();return 0; }