#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#define N 5010
#define inf 1<<31-1
using namespace std;
int dis[2][N];
struct node{
   int to;
   int dis;
};
vector<node>mp[N];
queue<int>q;
bool in_q[N];
int spfa(int st,int ed)
{
    int i,ui,si,mdis;
    for(i=0;i<=ed+9;i++)
    {
        in_q[i]=false;
        dis[0][i]=dis[1][i]=inf;
    }
    while(!q.empty())
        q.pop();
    q.push(st);
    in_q[st]=true;
    dis[0][st]=0;
    while(!q.empty())
    {
        si=q.front();
        q.pop();
        in_q[si]=false;
        for(i=0;i<mp[si].size();i++)
        {
            ui=mp[si][i].to;
            mdis=mp[si][i].dis+dis[0][si];
            if(mdis<dis[0][ui])
            {
                dis[1][ui]=dis[0][ui];
                dis[0][ui]=mdis;
                if(!in_q[ui]){
                    q.push(ui);
                    in_q[ui]=true;
                }
            }
            else{
                if(mdis<dis[1][ui]&&mdis!=dis[0][ui])
                dis[1][ui]=mdis;
            }
            if(dis[1][si]+mp[si][i].dis<dis[1][ui])
                dis[1][ui]=dis[1][si]+mp[si][i].dis;
        }
    }
    return dis[1][ed];
}
int main()
{
    int n,m,ans;
    int i,a,b,d;
    node temp;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=0;i<=n;i++)
            mp[i].clear();
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&d);
            temp.dis=d;
            temp.to=b;
            mp[a].push_back(temp);
            temp.to=a;
            mp[b].push_back(temp);
        }
        ans=spfa(1,n);
//        for(i=1;i<=n;i++)
//            printf("%d %d\n",dis[0][i],dis[1][i]);
        printf("%d\n",ans);
    }
    return 0;
}