#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
 
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) (s).rbegin(), (s).rend()
#define MP make_pair
#define X first
#define Y second
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;

void fin(){
	freopen("test.txt", "r", stdin);
}

const int INF = 1 << 29;

struct state{
	int ticket; // 0 => 未使用 1 => 使用中 2 => 使用済み
	int cost;
	int pos;

	state(int t = 0, int c = 0, int p = 0){
		ticket = t; cost = c; pos = p;
	}

	bool operator<(const state &r) const{
		return cost > r.cost;
	}
};

int main(){
	//fin();
	while(1){
		int n, m;
		cin >> n >> m;
		if(!n) break;
		n++;
		vector<vi> edge(n, vi(n, INF));
		rep(i, m){
			int a, b, c;
			cin >> a >> b >> c;
			edge[a][b] = edge[b][a] = c;
		}

		vector<vi> cost(3, vi(n, INF));

		priority_queue<state> q;
		q.push(state(0, 0, 1));

		while(!q.empty()){
			state s = q.top(); q.pop();

			if(cost[s.ticket][s.pos] <= s.cost) continue;
			cost[s.ticket][s.pos] = s.cost;
			if(s.ticket != 1 && s.pos == n) break;

			rep(i, n){
				if( edge[s.pos][i] == INF) continue;
				state next = s;
				next.pos = i;
				if( s.ticket == 0){
					next.ticket += 1;
					q.push(next);
					next.ticket -= 1;
					next.cost += edge[s.pos][i];
					q.push(next);
				}
				else if( s.ticket == 1){
					next.ticket += 1;
					q.push(next);
				}else{
					next.cost += edge[s.pos][i];
					q.push(next);
				}
			}
		}
		int ans = INF;
		ans = min(cost[0][n-1], cost[2][n-1]);

		cout << ans << endl;
	}

	return 0;
}