#include <bits/stdc++.h>

//{{{ graph.hpp
#ifndef INCLUDE_GRAPH_HPP
#define INCLUDE_GRAPH_HPP
#include <vector>
namespace orislib {
struct Edge {
  typedef int weight_t;
  int from, to;
  weight_t w;
  int ticket;
  Edge(int from, int to, weight_t w, int ticket=0) : from(from), to(to), w(w), ticket(ticket) {}
  bool operator<(const Edge& e) const {
    return w != e.w ? w > e.w : from != e.from ? from < e.from : to < e.to;
  }
  static const weight_t INF;
};
const int Edge::INF=INT_MAX;
typedef std::vector<Edge> Edges;
typedef std::vector<Edges> Graph;
}
#endif
//}}}

using namespace std;
using namespace orislib;

typedef long long ll;
typedef long double ld;
typedef tuple<int, int> duo;
const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int Mod = 1000000000 + 0;
//{{{ templates
#define TT_ template<typename T>inline
#define TTF_ template<typename T,typename F>inline
TT_ T sq(T x){return x*x;}
TT_ T In(){T x;cin>>x;return x;}
TT_ void Out(T&x){cout<<x;}
TT_ void sort(T&v){sort(begin(v),end(v));}
TT_ void revs(T&v){reverse(begin(v),end(v));}
TT_ void uniq(T&v){sort(v);v.erase(unique(begin(v),end(v)),end(v));}
TT_ int ubnd(T&v,typename T::value_type&x){return upper_bound(begin(v),end(v),x)-begin(v);}
TT_ int lbnd(T&v,typename T::value_type&x){return lower_bound(begin(v),end(v),x)-begin(v);}
TTF_ void inpt(T&v,int n,F f){for(v.reserve(n);n--;v.emplace_back(f()));}
TTF_ void show(T&v,F f,string d=" ",string e="\n"){int i=0;for(auto&x:v)i++&&(cout<<d),f(x);cout<<e;}
TT_ typename T::iterator minel(T&v){return min_element(begin(v),end(v));}
TT_ typename T::iterator maxel(T&v){return max_element(begin(v),end(v));}

inline void fast_io(){ios::sync_with_stdio(0);cin.tie(0);}
inline int in(){int x;scanf("%d",&x);return x;}
inline ll pow_mod(ll a,ll k,ll m){ll r=1;for(;k>0;a=a*a%m,k>>=1)if(k&1)r=r*a%m;return r;}
inline ll mod_inv(ll a,ll p){return pow_mod(a,p-2,p);}
//}}} priority_queue queue deque front stringstream max_element min_element insert count make_tuple

//{{{ void dijkstra(g, s, &dist, &prev)
void dijkstra(const Graph& g, int s, vector<Edge::weight_t>& distt)
{
  const int V = g.size();
  int dist[128][3];
  for (int i = 0; i < 128; i++){
    for (int j = 0; j < 3; j++){
      dist[i][j] = 1 << 29;
    }
  }
  int vis[128][3] = {};
  dist[s][0] = 0;
  priority_queue<Edge> pq;
  for (pq.push(Edge(-2, s, 0)); !pq.empty();){
    Edge c = pq.top();
    pq.pop();
    if (vis[c.to][c.ticket]) continue;
    vis[c.to][c.ticket] = 1;
    for (const auto& e : g[c.to]){
      if (c.ticket == 1){
        if (dist[e.to][2] > c.w){
          dist[e.to][2] = c.w;
          pq.push(Edge(e.from, e.to, c.w, 2));
        }
      }
      else if (dist[e.to][c.ticket] > e.w + c.w){
        dist[e.to][c.ticket] = e.w + c.w;
        pq.push(Edge(e.from, e.to, e.w + c.w, c.ticket));
      }
      if (c.ticket == 0){
        if (dist[e.to][1] > c.w){
          dist[e.to][1] = c.w;
          pq.push(Edge(e.from, e.to, c.w, 1));
        }
      }
    }
  }
  distt.assign(V, 1 << 29);
  for (int i = 0; i < V; i++){
    distt[i] = min(dist[i][0], dist[i][2]);
  }
}
//}}}


int main()
{
  int n, m;
  while (cin >> n >> m, n || m){
    Graph g(n + 1);
    for (int i = 0; i < m; i++){
      int a, b, c;
      cin >> a >> b >> c;
      g[a].emplace_back(a, b, c);
      g[b].emplace_back(b, a, c);
    }
    vector<int> ws;
    dijkstra(g, 1, ws);
    cout << ws[n] << endl;
  }
  return 0;
}

Measured memory_bytes: 1216