#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//

int N, M;
vector<pii> g[100];
int d[100][2];

int main() {
	while (cin >> N >> M, N || M) {
		REP(i, N) g[i].clear();
		
		REP(i, M) {
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			a--; b--;
			g[a].push_back(pii(b, c));
			g[b].push_back(pii(a, c));
		}
		
		vector<pii> add_edge;
		REP(i, N) {
			queue<int> que;
			REP(j, g[i].size()) que.push(g[i][j].fi);
			
			bool done[100] = {};
			while (!que.empty()) {
				int u = que.front(); que.pop();
				REP(j, g[u].size()) done[g[u][j].fi] = true;
			}
			
			REP(j, N) if (done[j]) add_edge.push_back(pii(i, j));
		}
		
		REP(i, add_edge.size()) {
			pii &e = add_edge[i];
			g[e.fi].push_back(pii(e.se, 0));
		}
		
		fill(d[0], d[N], INF);
		
		priority_queue<pip, vector<pip>, greater<pip> > pq; // cost, pos, state
		pq.push(pip(0, pii(0, 0)));
		d[0][0] = 0;
		
		while (!pq.empty()) {
			pip now = pq.top(); pq.pop();
			
			int cost = now.fi;
			int u = now.se.fi;
			int s = now.se.se;
			
			if (d[u][s] < cost) continue;
			
			REP(i, g[u].size()) {
				int v = g[u][i].fi;
				int c = g[u][i].se;
				
				if (c == 0) {
					if (s == 0 && chmin(d[v][1], cost)) pq.push(pip(cost, pii(v, 1)));
				}
				else {
					if (chmin(d[v][s], cost + c)) pq.push(pip(cost + c, pii(v, s)));
				}
			}
		}
		
		int ans = min(d[N - 1][0], d[N - 1][1]);
		cout << ans << endl;
	}

	
	return 0;
}