#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=1e9;
const int MOD=100000;
int B=1000000;
struct edge{int to,cost;};
int N,M;
int d[100][100];
vector<edge>G[100];
void dijkstra(int s){
      d[s][s]=0;
      priority_queue<P,vector<P>,greater<P> >Q;
      Q.push(P(0,s));
      while(!Q.empty()){
            P p=Q.top();Q.pop();
            int v=p.second;
            if(p.first>d[s][v])continue;
            for(int i=0;i<G[v].size();i++){
                  edge e=G[v][i];
                  if(d[s][e.to]>d[s][v]+e.cost){
                        d[s][e.to]=d[s][v]+e.cost;
                        Q.push(P(d[s][e.to],e.to));
                  }
            }
      }
}
int main(){
      while(cin>>N>>M&&(N||M)){
            REP(i,N)G[i].clear();
            REP(i,100)REP(j,100)d[i][j]=INF;
//            REP(i,N)REP(j,N)printf("%d%c",d[i][j],j==N-1?'\n':' ');
            REP(i,M){
                  int a,b,c;
                  cin>>a>>b>>c;a--;b--;
                  G[a].PB((edge){b,c});
                  G[b].PB((edge){a,c});
            }
            REP(i,N)dijkstra(i);
            vector<P>V;
            set<P> f;
            REP(i,N){
                  REP(j,G[i].size()){
                        int mid=G[i][j].to;
                        REP(k,G[mid].size()){
                              if(f.count(P(i,G[mid][k].to))==0){
                                    f.insert(P(i,G[mid][k].to));
                                    V.PB(P(i,G[mid][k].to));
                              }
                        }
                  }
            }
            int ans=INF;
            REP(i,V.size()){
                  if(ans>d[0][V[i].first]+d[V[i].second][N-1]){
                        ans=d[0][V[i].first]+d[V[i].second][N-1];
//                        cout<<V[i].first<<" "<<V[i].second<<" "<<ans<<endl;
                  }
            }
            cout<<ans<<endl;
      }
}