#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
void rp(int &n, int m){
  n = min(n, m);
}
struct S{
  int u, t, p;
  S(int u, int t, int p) :
    u(u), t(t), p(p) {}
  S() {}
  bool operator < (const S& s) const{
    return t > s.t;
  }
};

int main(){
  int n, m;
  while(cin>>n>>m && n){
    int d[100][100];
    REP(i, n)REP(j, n)d[i][j] = INF;
    REP(i, m){
      int u, v, c; cin>>u>>v>>c;
      u--; v--;
      d[u][v] = c;
      d[v][u] = c;
    }
    int dist[100][2];
    REP(i, n)dist[i][0] = dist[i][1] = INF;
    dist[0][0] = 0;
    priority_queue<S> que;
    que.push(S(0, 0, 0));
    while(!que.empty()){
      S s = que.top(); que.pop();
      if(s.u == n-1){
        cout<<s.t<<endl;
        break;
      }
      REP(to, n) if(d[s.u][to] != INF){
        int nt = s.t + d[s.u][to];
        if(dist[to][s.p] > nt){
          dist[to][s.p] = nt;
          que.push(S(to, nt, s.p));
        }
        if(s.p < 1){
          REP(to2, n)if(d[to][to2] != INF){
            int nt = s.t;
            if(dist[to2][1] > nt){
              dist[to2][1] = nt;
              que.push(S(to2, nt, 1));
            }
          }
        }
      }
    }
  }
  return 0;
}