#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <string>
using namespace std;
#define rep(I,N) for(int I = 0; I < (int)(N); I++)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)
typedef pair<int, int> P;
typedef long long ll;
typedef priority_queue<int> pq;

struct Data{
	int pass, pos, cost;
	Data(int _pass, int _pos, int _cost){
		pass = _pass;
		pos = _pos;
		cost = _cost;
	}
	Data(){}
};
int map[102][102];
int memo[102][3];
int main(void){
	int n, m;
	while(cin >> n >> m, n){
		int mini = INF;
		int co;
		fill_n(*map, 102*102, INF);
		fill_n(*memo, (102)*3, INF);
		rep(i, m){
			int a, b, c;
			cin >> a >> b;
			cin >> c;
			co = c;
			map[a][b] = c;
			map[b][a] = c;
		}
		if(m == 1){
			FIN(co);
			continue;
		}
		queue<Data> que;
		que.push(Data(0, 1, 0));
		while(!que.empty()){
			Data data = que.front();
			que.pop();
			int pos = data.pos;
			int cost = data.cost;
			int pass = data.pass;
			if(memo[pos][pass] <= cost)continue;
			memo[pos][pass] = cost;
			for(int i = 1; i <= 101; i++){
				if(map[pos][i] != INF){
					if(pass == 1){
						que.push(Data(2, i, cost));
					}else{
						que.push(Data(pass, i, cost+map[pos][i]));
						if(pass == 0){
							que.push(Data(1, i, cost));
						}
					}

				}

			}
		}
		FIN(min(memo[n][0],memo[n][2]));
	}
	return 0;
}