//给一个无向图，问删除一条边，使得从1到n的最短路最长

//问这个最长路

//这个删除的边必定在最短路上，假设不在。那么走这条最短路肯定比其它短

//枚举删除这条最短路的边，找其最长的即为答案

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std ;

const int maxn = 1110 ;

const int inf = 0x3f3f3f3f;

struct Edge

{

    int u , v , w ;

    int next ;

}edge[maxn*maxn] ;

int head[maxn] ;

int nedge ;

int F[maxn] ;

int vis[maxn] ;

int dis[maxn] ;

int a[maxn] ;

int n , m;

void addedge(int u , int v , int w)

{

    edge[nedge].u = u ;

    edge[nedge].v = v ;

    edge[nedge].w = w ;

    edge[nedge].next = head[u] ;

    head[u] = nedge++ ;

}

void dijkstra(int num)

{

    memset(vis , 0 , sizeof(vis)) ;

    for(int j = 2;j <= n;j++)

    dis[j] = inf ;

    dis[1] = 0 ;

    while(1)

    {

        int mi = inf; int pos ;

        for(int j = 1 ;j <= n;j++)

        if(!vis[j] && dis[j] < mi)

        mi = dis[pos = j] ;

        if(mi == inf)break;

        vis[pos] = 1 ;

        for(int i = head[pos] ;i != -1 ;i = edge[i].next)

        {

            if(i == num || i == (num^1))

            continue ;

            int v = edge[i].v;

            if(dis[v] > dis[pos] + edge[i].w)

            {

                dis[v] = dis[pos] + edge[i].w ;

                F[v] = i ;

            }

        }

    }

}

int main()

{

    //freopen("in.txt" ,"r" , stdin) ;

    while(~scanf("%d%d" , &n , &m))

    {

        memset(head , -1 , sizeof(head)) ;

        nedge = 0 ;

        memset(F , 0 , sizeof(F)) ;

        while(m--)

        {

            int u , v , w ;

            scanf("%d%d%d" ,&u , &v ,&w) ;

            addedge(u , v , w) ;

            addedge(v , u , w) ;

        }

        dijkstra(nedge) ;

        int u = n ;

        int ans = 0 ;

        int len = 0 ;

        while(1)

        {

            if(u == 1)break ;

            a[++len] = F[u] ;

            u = edge[F[u]].u ;

        }

        for(int i = 1;i <= len;i++)

        {

            dijkstra(a[i]) ;

            ans = max(ans , dis[n]) ;

        }

        cout<<ans<<endl;

    }

    return  0 ;

}