#include<bits/stdc++.h>
using namespace std;
const int mn=1010;
const int inf=0x3f3f3f3f;
const int mm=1000*999+10;
int tot,n,m,maxn,r;
int dis[mn],vis[mn],f[mn];
int f1[mn];
int read()
{
    int sum=0;
    int f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        sum*=10;
        sum+=c-'0';
        c=getchar();
    }
    return sum*f;
}
struct point
{
    int v,w,next;
}e[mm];
int head[mm];
void rd(int u,int v,int w)
{
    tot++;
    e[tot].next=head[u];
    head[u]=tot;
    e[tot].v=v;
    e[tot].w=w;
}
struct node
{
    int spot;
    int distan;
    bool operator < (const node &x)const
    {
        return distan>x.distan;
    }
};
void dij1()
{
    priority_queue< node > q;
    q.push(node{1,0});
    for(int i=1;i<=n;i++)
    {
        dis[i]=inf;
        vis[i]=1;
        f[i]=i;
    }
    dis[1]=0;
    vis[1]=0;
    while(vis[n]==1)
    {
        node u=q.top();
        q.pop();
        vis[u.spot]=0;
        for(int i=head[u.spot];i!=0;i=e[i].next)
        {
            int v=e[i].v;
            if(dis[v]>dis[u.spot]+e[i].w)
            {
                dis[v]=dis[u.spot]+e[i].w;
                q.push(node{v,dis[v]});
                f[v]=u.spot;
            }
        }

    }
    int i=n;r=1;
    while(i!=1)
    {

        f1[r]=i;r++;
        i=f[i];
    }
    f1[r]=1;
}
void dij2(int x,int y)
{
    priority_queue< node > q;
    q.push(node{1,0});
    for(int i=1;i<=n;i++)
    {
        dis[i]=inf;
        vis[i]=1;
    }
    dis[1]=0;
    vis[1]=0;
    while(vis[n]==1)
    {
        node u=q.top();
        q.pop();
        vis[u.spot]=0;
        for(int i=head[u.spot];i!=0;i=e[i].next)
        {
            int v=e[i].v;
            if((u.spot==x&&v==y)||(u.spot==y&&v==x))continue;
            if(dis[v]>dis[u.spot]+e[i].w)
            {
                dis[v]=dis[u.spot]+e[i].w;
                q.push(node{v,dis[v]});
                f[v]=u.spot;
            }
        }
    }
    if(dis[n]>maxn)maxn=dis[n];
}
int main()
{
    n=read();
    m=read();
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read();
        v=read();
        w=read();
        rd(u,v,w);
        rd(v,u,w);
    }
    dij1();
    for(int i=2;i<=r;i++)
    {
        dij2(f1[i-1],f1[i]);
    }
    cout<<maxn;
    return 0;
}