#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;
}

大佬康康为甚样例未过