#include<iostream> #include<cstring> #include<cstdio> using namespace std; struct data{ int from,to,next,w; }e[1000001]; int n,m,sum=0,head[1001],dis[1001],ans,father[1001],q[1000001]; bool del[1000001],inq[1001]; void insert(int u,int v,int w) { sum++; e[sum].from=u; e[sum].to=v; e[sum].next=head[u]; e[sum].w=w; head[u]=sum; } void spfa(int k) { memset(dis,127,sizeof(dis)); memset(inq,0,sizeof(inq)); memset(q,0,sizeof(q)); int t=0,w=1,now; q[t]=1;inq[1]=1;dis[1]=0; while(t<w){ int p=head[q[t]]; now=q[t];t++; while(p){ if(!del[p]&&dis[now]+e[p].w<dis[e[p].to]){ dis[e[p].to]=dis[now]+e[p].w; if(k==1)father[e[p].to]=p; if(!inq[e[p].to]){ inq[e[p].to]=1; q[w++]=e[p].to; } } p=e[p].next; } inq[now]=0; } } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++){ int a,b,v; scanf("%d %d %d",&a,&b,&v); insert(a,b,v); insert(b,a,v); } spfa(1); for(int i=n;i!=1;i=e[father[i]].from){ del[father[i]]=1;spfa(0);del[father[i]]=0; ans=max(dis[n],ans); } printf("%d",ans); return 0; }