#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
typedef pair<pii,int>piii;
int main(){
    int n,m;
    while(cin>>n>>m,n+m){
        vvi hoge(n+1,vi(n+1,INF));
        //edge[index]=(distance,next_vertex)
        vector<vector<pii>>edge(n,vector<pii>());
        vector<vector<pii>>temp(n,vector<pii>());
        rep(i,m){
            int a,b,c; cin>>a>>b>>c;
            --a,--b;
            edge[a].push_back(pii(b,c));
            edge[b].push_back(pii(a,c));
        }
        vvi d(3,vi(n,INF));
        d[0][0]=0;
        priority_queue<piii,vector<piii>,greater<piii>>que;
        que.push(piii(pii(0,0),0));
        
        while(!que.empty()){
            piii now=que.top();que.pop();
         //   cout<<now.first.first<<" "<<now.first.second<<" "<<now.second<<endl;
            for(int i=0; i<edge[now.second].size();i++){
                pii next=edge[now.second][i];
                if(now.first.second==0){
                    if(now.first.second==0&&d[0][next.first]>d[0][now.second]+next.second){
                        que.push(piii(pii(d[0][now.second]+next.second,0),next.first));
                        d[0][next.first]=d[0][now.second]+next.second;
                    }
                    if(now.first.second==0){
                        d[1][next.first]=d[0][now.second];
                        que.push(piii(pii(now.first.first,1),next.first));
                    }
                }else if(now.first.second==1){
                    if(d[2][next.first]>d[1][now.second]){
                        que.push(piii(pii(d[1][now.second],2),next.first));
                        d[2][next.first]=d[1][now.second];
                    }
                }else if(now.first.second==2&&d[2][next.first]>d[2][now.second]+next.second){
                    d[2][next.first]=d[2][now.second]+next.second;
                    que.push(piii(pii(now.first.first+next.second,2),next.first));
                }
            }
        }
        cout<<min(d[0][n-1],d[2][n-1])<<endl;
    }
}