#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <cstdio>
#include <set>

using namespace std;

inline int getInt(){ int s; scanf("%d", &s); return s; }

int main(){
  while(true){
    const int n = getInt();
    const int m = getInt();

    if(n + m == 0) break;

    const int MAX = 100000;
    vector<vector<int> > g(n, vector<int>(n, MAX));
    vector<vector<int> > dp(n, vector<int>(3, -1));

    REP(i,m){
      const int a = getInt() - 1;
      const int b = getInt() - 1;
      const int c = getInt();

      g[a][b] = min(g[a][b], c);
      g[b][a] = min(g[b][a], c);
    }

    typedef pair<int, pair<int, int> > data;
    priority_queue<data, vector<data>, greater<data> > pq;

    pq.push(make_pair(0, make_pair(0, 0)));

    while(pq.size()){
      const data d = pq.top(); pq.pop();
      const int cost = d.first;
      const int pos  = d.second.first;
      const int cnt  = d.second.second;

      if(cnt != 1 && pos == n - 1){
        printf("%d\n", cost);
        break;
      }

      if(dp[pos][cnt] != -1) continue;
      dp[pos][cnt] = cost;

      REP(i,n) if(g[pos][i] != MAX){
        if(cnt == 1){
          if(dp[i][2] == -1){
            pq.push(make_pair(cost, make_pair(i, 2)));
          }
        }else{
          if(cnt == 0){
            if(dp[i][1] == -1){
              pq.push(make_pair(cost, make_pair(i, 1)));
            }
          }
          if(dp[i][cnt] == -1){
            pq.push(make_pair(cost + g[pos][i], make_pair(i, cnt)));
          }
        }
      }
    }
  }
  return 0;
}