#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
typedef vector<int> Vi;
typedef pair<int,int> Pii;
typedef pair<int,Pii> Pip;
const int INF = (1<<25);
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

struct edge {
  int to, cost;
  edge(int to_, int cost_) {
    to = to_; cost = cost_;
  }
};

vector<edge> G[101];
int n, m;

int dij() {
  int d[2][101];
  for(int i=0; i<101; i++) {
    d[0][i] = d[1][i] = INF;
  }

  priority_queue<Pip, vector<Pip>, greater<Pip> > q;
  q.push(Pip(0, Pii(0, 1)));
  d[0][0] = 0;
  while( !q.empty() ) {
    Pip p = q.top(); q.pop();
    int cost = p.fr, u = p.sc.fr, t = p.sc.sc;

    if( u == n-1 ) {
      return cost;
    }

    for(int i=0; i<G[u].size(); i++) {
      int v = G[u][i].to;
      int add_cost = G[u][i].cost;
      if( cost + add_cost < d[t][v] ) {
	d[t][v] = cost + add_cost;
	q.push(Pip(d[t][v], Pii(v, t)));
      }

      if( t ) {
	for(int j=0; j<G[v].size(); j++) {
	  int k = G[v][j].to;
	  if( cost < d[t-1][k] ) {
	    d[t-1][k] = cost;
	    q.push(Pip(d[t-1][k], Pii(k, t-1)));
	  }
	}
      }
    }
  }
}

int main() {
  while( cin >> n >> m, n+m ) {
    for(int i=0; i<101; i++) {
      G[i].clear(); 
    }

    for(int i=0; i<m; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      a--; b--;
      G[a].pb(edge(b, c));
      G[b].pb(edge(a, c));
    }

    cout << dij() << endl;
  }
}