#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> PP;
#define INF (1<<25)
int N,M;
struct edge{
  int to,c;
  edge(int to,int c) : to(to),c(c) {}
};

vector<edge> G[102];
int H[102][3];

void solve(){
  priority_queue<PP,vector<PP>,greater<PP> > q;
  while(!q.empty()) q.pop();
  for(int i=0;i<102;i++){
    H[i][0]=INF; H[i][1]=INF; H[i][2]=INF;
  }

  q.push( PP(0,P(1,0)) );
  while(!q.empty()){
    PP p = q.top(); q.pop();
    int ind = p.second.first;
    int in = p.second.second;
    int cost = p.first;
    for(int i=0;i<(int)G[ind].size();i++){
      edge e = G[ind][i];
      if(in == 0){
	if(H[e.to][1] > cost){
	  q.push( PP(cost,P(e.to,1)) );
	  H[e.to][1] = cost;
	}
	if(H[e.to][in] > cost + G[ind][i].c){
	  q.push( PP(cost+G[ind][i].c,P(e.to,in)) );
	  H[e.to][in] = cost+G[ind][i].c;
	}
      }else if(in == 1){
	if(H[e.to][2] > cost){
	  q.push( PP(cost,P(e.to,2)) );
	  H[e.to][2] = cost;
	}
      } else {
	if(H[e.to][in] > cost + G[ind][i].c){
	  q.push( PP(cost+G[ind][i].c,P(e.to,in)) );
	  H[e.to][in] = cost+G[ind][i].c;
	}
      }
    }
  }
}

int main(){
  while(1){
    scanf("%d %d",&N,&M);
    if(!N && !M) break;
    for(int i=0;i<M;i++){
      int a,b,c;
      scanf("%d %d %d",&a,&b,&c);
      G[a].push_back(edge(b,c));
      G[b].push_back(edge(a,c));
    }
    solve();
    printf("%d\n",min(H[N][0],H[N][2]));
    for(int i=0;i<102;i++) G[i].clear();
  }
}