#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
inline void output(int x)
{
	if(x>9) output(x/10);
	putchar(x%10^48);
	return;
}
const int MAXN=1010;
const int MAXM=1e6+10;
int n,m,ans;
int x[MAXM],y[MAXM],z;
int head[MAXN],tot,d[MAXN];
bool vis[MAXN][MAXN];
inline int Max(int x,int y){return x>y?x:y;}
struct edge
{
	int to,cost;
	edge(int to,int cost):to(to),cost(cost){}
};
vector<edge>G[MAXN];
typedef pair<int,int>P;
inline void dijkstra(int s)
{
	priority_queue<P,vector<P>,greater<P> >q;
	for(register int i=1;i<=n;i++) d[i]=1e9;
	d[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty())
	{
		P p=q.top();
		q.pop();
		int v=p.second;
		if(d[v]<p.first) continue;
		for(register int i=0;i<G[v].size();i++)
		{
			edge e=G[v][i];
			if(!vis[v][e.to]) continue;
			if(d[e.to]>d[v]+e.cost)
			{
				d[e.to]=d[v]+e.cost;
				q.push(make_pair(d[e.to],e.to));
			}
		}
	}
	return;
}
int main()
{
	n=read(),m=read();
	for(register int i=1;i<=m;i++)
	{
		x[i]=read(),y[i]=read(),z=read();
		G[x[i]].push_back(edge(y[i],z));
		G[y[i]].push_back(edge(x[i],z));
		vis[x[i]][y[i]]=vis[y[i]][x[i]]=true;
	}
	for(register int i=1;i<=m;i++)
	{
		int u=x[i],v=y[i];
		vis[u][v]=vis[v][u]=false;
		dijkstra(1);
		ans=Max(ans,d[n]);
		vis[u][v]=vis[v][u]=true;
	}
	printf("%d\n",ans);
	return 0;
}