#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef pair<int,int>  pi;

struct Edge { int to, cost; };
vector<Edge> G[3000];
int d[3000];

int main() {
	int n, m;
	while (cin >> n >> m, n) {
		fill(G, G+3000, vector<Edge>());
		int a, b, c;
		for (int i=0; i<m; ++i) {
			cin >> a >> b >> c;
			--a, --b;
			G[a].push_back((Edge){b, c});
			G[b].push_back((Edge){a, c});
			G[a].push_back((Edge){b+1000, 0});
			G[b].push_back((Edge){a+1000, 0});
			G[a+1000].push_back((Edge){b+2000, 0});
			G[b+1000].push_back((Edge){a+2000, 0});
			G[a+2000].push_back((Edge){b+2000, c});
			G[b+2000].push_back((Edge){a+2000, c});
		}
		fill(d, d+3000, INT_MAX);
		d[0] = 0;
		priority_queue<pi, vector<pi>, greater<pi> > q;
		q.push(make_pair(0, 0));
		while ( ! q.empty()) {
			int dist = q.top().first;
			int v = q.top().second;
			q.pop();
			for (int i=0; i<(int)G[v].size(); ++i) {
				Edge &e = G[v][i];
				if (dist + e.cost < d[e.to]) {
					d[e.to] = dist + e.cost;
					q.push(make_pair(d[e.to], e.to));
				}
			}
		}
		cout << min(d[n-1], d[n-1+2000]) << endl;
	}
	return 0;
}