#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>#include <cmath>#include <cstring>using namespace std;#define INF 0xfffffff#define maxn 5060struct Edge{    int e, w;    Edge(int e=0,int w=0): e(e), w(w) {}};int n, m;int dist[2][maxn];int vis[maxn];vector<Edge> G[maxn];void  Spfa(int Star,int k){    Edge P, Pn;    queue <Edge> Q;    dist[k][Star] = 0;    Q.push( Edge(Star,0) );    while( !Q.empty() )    {        P = Q.front();        Q.pop();        vis[P.e] = false;        int len = G[P.e].size();        for(int i=0; i<len; i++)        {            Pn = G[P.e][i];            if(dist[k][Pn.e] > dist[k][P.e] + Pn.w )            {                dist[k][Pn.e] = dist[k][P.e] + Pn.w;                if(!vis[Pn.e] )                {                    Q.push(Pn);                    vis[Pn.e] = true;                }            }        }    }}int Slove(){    int ans = INF;    int Min = dist[0][n];    Edge P;    for(int i=1; i<=n; i++)    {        int len = G[i].size();        for(int j=0; j<len; j++)        {            P = G[i][j];            int temp = dist[0][i] + dist[1][P.e] + P.w;            if(temp > Min && temp < ans)                ans = temp;        }    }    return ans;}void Init(){    for(int i=1; i<=n; i++)    {        G[i].clear();        vis[i] = false;        dist[0][i] = dist[1][i] = INF;    }}int main(){    while(cin >> n >> m)    {        int a, b, c;        Init();        for(int i=0; i<m; i++)        {            scanf("%d%d%d",&a,&b,&c);            G[a].push_back( Edge(b,c) );            G[b].push_back( Edge(a,c) );        }        Spfa(1,0);        Spfa(n,1);        int ans = Slove();        cout << ans << endl;    }    return 0;}