#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,m,a,b,w,k=0,ans=0;
int head[1005];
int dis[1005];
int visit[1005];
int side[1005];
struct node
{
int to,w,next,front;
}mp[500005];
void adde(int u,int v,int w)
{
mp[++k].to=v;
mp[k].w=w;
mp[k].next=head[u];
head[u]=k;
mp[k].front=u;
}
void dijkstra(bool ft)
{
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
dis[1]=0;
q.push(make_pair(dis[1],1));
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(visit[u]==1) continue;
visit[u]=1;
for(int i=head[u];i!=-1;i=mp[i].next)
{
int to=mp[i].to;
if(dis[to]>dis[u]+mp[i].w)
{
dis[to]=dis[u]+mp[i].w;
if(ft)
side[to]=i;
q.push(make_pair(dis[to],to));
}
}
}
}
int main()
{
cin>>n>>m;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
dis[i]=999999;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>w;
adde(a,b,w);
adde(b,a,w);
}
dijkstra(1);
int kk=n;
while(kk!=1)
{
int mm=mp[side[kk]].w;
mp[side[kk]].w=999999;
dijkstra(0);
ans=max(ans,dis[n]);
mp[side[kk]].w=mm;
kk=mp[side[kk]].front;
}
cout<<ans;
return 0;
}
大佬康康为甚样例未过