// Slower C++ solution:
#include <stdio.h>

#include <cctype>

#include <limits.h>

#include <math.h>

#include <complex>

#include <bitset>

#include <vector>

#include <map>

#include <set>

#include <stack>

#include <queue>

#include <cstring>

#include <string>

#include <sstream>

#include <algorithm>

#include <iomanip>

#include <iostream>



#define VARIABLE(x) cerr << #x << "=" << x << endl

#define BINARY(x) static_cast<bitset<16> >(x);

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

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

#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))



const int INF = 1000000000;

const double EPS = 1e-8;

const double PI = 3.14159;

int dx[4]={0, 1, 0, -1}, dy[4]={-1, 0, 1, 0};

using namespace std;

//typedef pair<int, int> P;

struct P {

	int x, y;

	P(int x, int y):x(x), y(y){}

	P(){}

};



/** Problem0244 : Hot Spring Trip **/

int cost[300][300];



int main()

{

	int N, M;

	

	while (cin>>N>>M, N||M) {

		rep(i, 300) rep(j, 300)

			cost[i][j] = i==j?0:INF;

	

		rep(i, M) {

			int a, b, c; cin>>a>>b>>c;

			a--, b--;

			cost[a][b] = cost[b][a] = c;

		}

		

		vector<P> can_free;

		rep(i, N) {

			rep(j, N) {

				if (cost[i][j]!=INF && i!=j) {

					rep(k, N) {

						if (cost[j][k]!=INF && i!=k && j!=k)

							can_free.push_back(P(i, k));

					}

				}

			}

		}

		

		rep(k, N) {

			rep(i, N) {

				rep(j, N) {

					cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);

				}

			}

		}

		

		int ans=cost[0][N-1];

		rep(i, can_free.size()) {

			ans = min(cost[0][can_free[i].x]+cost[can_free[i].y][N-1], ans);

		}

		

		cout << ans << endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.4227908691544235x):
#include <bits/stdc++.h>



#define DEBUG(x) cerr << #x << "=" << x << endl

#define BINARY(x) static_cast<bitset<16> >(x)

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

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

#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

#define is_in(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

#define ALL(a) (a).begin(),(a).end()



int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

using namespace std;

typedef long long ll;

typedef vector<vector<int> > VVI;

const int INF = 1e9;

typedef pair<int, int> PII;



const int V_MAX = 100;



struct Edge {

    int to, cost;

    Edge(int _to, int _cost) : to(_to), cost(_cost) {}

};



vector<Edge> G[V_MAX];

vector<int> go_free[V_MAX];



struct State {

    int v, ticket, d;

    State (int _v, int _ticket, int _d) : v(_v), ticket(_ticket), d(_d) {}

    bool operator > (const State &b) const {return d > b.d;}

};



int main()

{

    int N, M;

    while (cin>>N>>M, N||M) {

        rep(i, N) G[i].clear();

        rep(i, N) go_free[i].clear();



        rep(i, M) {

            int A, B, C;

            cin >> A >> B >> C;

            A--, B--;

            G[A].emplace_back(B, C);

            G[B].emplace_back(A, C);

        }



        for (int i=0; i<N; i++) {

            for (auto g : G[i]) {

                for (auto h : G[g.to]) {

                    if (h.to != i) {

                        go_free[i].push_back(h.to);

                        // cerr << "free : (" << i << ", "<< h.to << ")" << endl;

                    }

                }

            }

        }



        priority_queue<State, vector<State>, greater<State>> Q;

        map<PII, int> d;



        d[PII(0, 1)] = 0;

        Q.push(State(0, 1, 0));



        int ans;

        while (Q.size()) {

            State s = Q.top(); Q.pop();

            // cerr << s.v << " " << s.ticket << " " << s.d << endl;

            

            if (s.v == N-1) {

                ans = s.d;

                break;

            }



            if (d.count(PII(s.v, s.ticket)) && d[PII(s.v, s.ticket)] < s.d) continue;



            // no ticket

            for (auto e : G[s.v]) {

                int new_cost = d[PII(s.v, s.ticket)] + e.cost;

                if (!d.count(PII(e.to, s.ticket)) || d[PII(e.to, s.ticket)] > new_cost) {

                    d[PII(e.to, s.ticket)] = new_cost;

                    Q.push(State(e.to, s.ticket, new_cost));

                }

            }



            // with ticket

            if (s.ticket) {

                for (auto i : go_free[s.v]) {

                    if (!d.count(PII(i, 0)) || d[PII(i, 0)] > s.d) {

                        d[PII(i, 0)] = s.d;

                        Q.push(State(i, 0, s.d));

                    }

                }

            }

        }



        cout << ans << endl;

    }

}