#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;

#define BIG_NUM 2000000000

using namespace std;

struct Node{

	Node(int arg_to,int arg_cost,bool isUsed){
		to = arg_to;
		cost = arg_cost;
		used = isUsed;
	}
	bool operator<(const struct Node &arg) const{
			return cost > arg.cost;
	};

	int to,cost;
	bool used;
};

void func(int N,int M){

	vector<Node> V[N+1],workV[N+1];

	int from,to,cost,D_used[N+1],D_unused[N+1];

	for(int i = 1; i <= N; i++){
		D_used[i] = BIG_NUM;
		D_unused[i] = BIG_NUM;
	}

	D_used[1] = 0;
	D_unused[1] = 0;

	for(int loop = 0; loop < M; loop++){
		scanf("%d %d %d",&from,&to,&cost);

		V[from].push_back(Node(to,cost,false));
		V[to].push_back(Node(from,cost,false));
	}

	int middle;

	for(int i = 1; i <= N; i++){
		for(int k = 0; k < V[i].size(); k++){
			middle = V[i][k].to;
			for(int p = 0; p < V[middle].size();p++){
				if(i != V[middle][p].to){
					workV[i].push_back(Node(V[middle][p].to,0,true));
				}
			}
		}
	}

	for(int i = 1; i <= N; i++){
		for(int k = 0; k < workV[i].size(); k++){
			V[i].push_back(workV[i][k]);
		}
	}

	priority_queue<Node> Q;

	for(int i = 0; i < V[1].size(); i++){
		if(V[1][i].used == false){
			D_unused[V[1][i].to] = V[1][i].cost;
		}else{
			D_used[V[1][i].to] = V[1][i].cost;
		}
		Q.push(Node(V[1][i].to,V[1][i].cost,V[1][i].used));
	}

	int min_index;
	while(!Q.empty()){
		if(Q.top().used == true){
			if(Q.top().cost == D_used[Q.top().to]){
				min_index = Q.top().to;
				Q.pop();
			}else{
				Q.pop();
				continue;
			}

			for(int k = 0; k < V[min_index].size(); k++){
				if(V[min_index][k].used == false){
					if(D_used[V[min_index][k].to] > D_used[min_index] + V[min_index][k].cost){
						D_used[V[min_index][k].to] = D_used[min_index] + V[min_index][k].cost;
						Q.push(Node(V[min_index][k].to,D_used[V[min_index][k].to],true));
					}
				}else{
					//Do nothing
				}
			}

		}else{
			if(Q.top().cost == D_unused[Q.top().to]){
				min_index = Q.top().to;
				Q.pop();
			}else{
				Q.pop();
				continue;
			}

			for(int k = 0; k < V[min_index].size(); k++){
				if(V[min_index][k].used == false){
					if(D_unused[V[min_index][k].to] > D_unused[min_index] + V[min_index][k].cost){
						D_unused[V[min_index][k].to] = D_unused[min_index] + V[min_index][k].cost;
						Q.push(Node(V[min_index][k].to,D_unused[V[min_index][k].to],false));
					}
				}else{
					if(D_used[V[min_index][k].to] > D_unused[min_index] + V[min_index][k].cost){
						D_used[V[min_index][k].to] = D_unused[min_index] + V[min_index][k].cost;
						Q.push(Node(V[min_index][k].to,D_used[V[min_index][k].to],true));
					}
				}
			}
		}
	}

	printf("%d\n",min(D_used[N],D_unused[N]));
}

int main(){

	int N,M;

	while(true){
		scanf("%d %d",&N,&M);
		if(N == 0 && M == 0)break;

		func(N,M);
	}

    return 0;
}