#include <queue>
#include <vector>
#include <iostream>
using namespace std;
struct edge {
	int to, cost, tp;
};
bool operator<(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}
int N, M, a, b, c;
int main() {
	while (cin >> N >> M, N) {
		vector<vector<edge> > G(N);
		for (int i = 0; i < M; i++) {
			cin >> a >> b >> c; a--, b--;
			G[a].push_back(edge{ b, c, 0 });
			G[b].push_back(edge{ a, c, 0 });
		}
		vector<vector<edge> > gt = G;
		for (int i = 0; i < N; i++) {
			vector<vector<bool> > dp(3, vector<bool>(N, false)); dp[0][i] = true;
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < N; k++) {
					if (!dp[j][k]) continue;
					for (edge e : gt[k]) dp[j + 1][e.to] = true;
				}
			}
			for (int j = 0; j < N; j++) {
				if (dp[2][j]) G[i].push_back(edge{ j, 0, 1 });
			}
		}
		priority_queue<edge> que; que.push(edge{ 0, 0, 0 });
		vector<vector<int> > dist(N, vector<int>(2, 999999999)); dist[0][0] = 0;
		while (!que.empty()) {
			edge u = que.top(); que.pop();
			for (edge e : G[u.to]) {
				int cost = dist[u.to][u.tp] + e.cost;
				int ntp = u.tp + e.tp;
				if (ntp == 2) continue;
				if (dist[e.to][ntp] > cost) {
					dist[e.to][ntp] = cost;
					que.push(edge{ e.to, -cost, ntp });
				}
			}
		}
		cout << min(dist[N - 1][0], dist[N - 1][1]) << endl;
	}
	return 0;
}