#include<bits/stdc++.h>
#define INF 0x3f
using namespace std;
int n,m,cnt,flag,ans;
int head[1005],dis[1005],cut[1005][1005],f[1005],a[1005];
struct Node{
    int to,Next,w;
}g[1000005];
void Insert(int u,int v,int w){
    g[++cnt].to=v;
    g[cnt].Next=head[u];
    head[u]=cnt;
    g[cnt].w =w;
}
void spfa(){
    queue<int> q;
    memset(a,0,sizeof(a));
    memset(dis,INF,sizeof(dis));
    q.push(1);
    dis[1]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        a[u]=0;
        for(int i=head[u];i;i=g[i].Next){
            if(cut[u][g[i].to]==0&&dis[g[i].to]>dis[u]+g[i].w){
                if(!flag)f[g[i].to]=u;
                dis[g[i].to]=dis[u]+g[i].w; 
                if(!a[g[i].to]){
                    a[g[i].to]=1;
                    q.push(g[i].to);
                }
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        Insert(u,v,w);
        Insert(v,u,w);
    }
    spfa();
    flag=1;
    for(int i=n;i!=1;i=f[i]){
        cut[f[i]][i]=1;
        cut[i][f[i]]=1;
        spfa();
        cut[f[i]][i]=0;
        cut[i][f[i]]=0;
        ans=ans>dis[n]?ans:dis[n];
    }
    cout<<ans;
    return 0;
}