#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
typedef pair<ll,P> P1;
const ll mod=1e9+7;

struct edge{
  ll to,cost;
};

ll inf=1e15;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(true){
      ll n,m;
      cin>>n>>m;
      if(n==0 && m==0) return 0;
      vector<vector<edge> > g(110);
      ll dist[110][3];
      rep(i,110)rep(j,3) dist[i][j]=inf;
      rep(i,m){
        ll a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
      }
      priority_queue<P1,vector<P1>,greater<P1> > que;
      que.push(P1(0,P(1,0)));
      while(!que.empty()){
        P1 p=que.top();
        que.pop();
        ll now=p.first;
        ll v=p.second.first,cnt=p.second.second;
        if(dist[v][cnt]<now) continue;
        for(auto itr:g[v]){
          if(cnt==0){
            if(dist[itr.to][0]>now+itr.cost){
              dist[itr.to][0]=now+itr.cost;
              que.push(P1(dist[itr.to][0],P(itr.to,0)));
            }
            if(dist[itr.to][1]>now){
              dist[itr.to][1]=now;
              que.push(P1(dist[itr.to][1],P(itr.to,1)));
            }
          }else if(cnt==1){
            if(dist[itr.to][2]>now){
              dist[itr.to][2]=now;
              que.push(P1(dist[itr.to][2],P(itr.to,2)));
            }
          }else{
            if(dist[itr.to][2]>now+itr.cost){
              dist[itr.to][2]=now+itr.cost;
              que.push(P1(dist[itr.to][2],P(itr.to,2)));
            }
          }
        }
      }
      cout<<dist[n][2]<<endl;
    }
}
