#include<iostream>
#include<cstdio>
#include<climits>
#include<cstring>
using namespace std;
int road[1005][1005];
int n,m;
int fa[1005];
int dist[1005];
int vis[1005];
int sum;
int Min(int a,int b)
{
    return a<b?a:b;
}
int Max(int a,int b)
{
    return a>b?a:b;
}
int dijk(int start,int last)
{
    for(int i=1;i<=n;i++)
    {
        dist[i]=INT_MAX;
    }
    dist[start]=0;
    memset(vis,0,sizeof(vis));
    for(int j=0;j<n;j++)
    {
        int m=INT_MAX,x;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&dist[i]<m)
            {
                m=dist[i];
                x=i;
            }
        }
        vis[x]=1;
        for(int i=1;i<=n;i++)
        {
            if(road[x][i]!=-1)
            {
                dist[i]=Min(dist[i],dist[x]+road[x][i]);
            }
        }
    }
    return dist[last];
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(road,-1,sizeof(road));
        for(int i=0;i<m;i++)
        {
            int start,last,temp;
            scanf("%d%d%d",&start,&last,&temp);
            road[start][last]=road[last][start]=temp;
        }
        int maxn=dijk(1,n);
        sum=0;
        int x=n;
        fa[sum++]=x;
        while(x!=1)
        {
            for(int i=1;i<=n;i++)
            {
                if(dist[i]==INT_MAX||road[i][x]==-1)continue;
                if(dist[x]==dist[i]+road[i][x])
                {
                    fa[sum++]=i;
                    x=i;
                    break;
                }
            }
        }
        for(int i=1;i<sum;i++)
        {
            int s=fa[i];
            int t=fa[i-1];
            int temp=road[s][t];
            road[s][t]=road[t][s]=-1;
            maxn=Max(maxn,dijk(1,n));
            road[s][t]=road[t][s]=temp;
        }
        printf("%d\n",maxn);
    }
    return 0;
}