#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1<<29)

int cost[100][100];

struct Node{
	int p;
	int s;	
	int cost;
	Node(){}
	Node(int a,int b,int c):p(a),s(b),cost(c){}
	bool operator<(const Node &a)const{return cost>a.cost;} 
};
int dijkstra(int n){
	int dp[100][3];
	priority_queue<Node> pq;
	Node a,b;
	fill_n((int*)dp,300,INF);
	a=Node(0,0,0);
	dp[a.p][a.s]=a.cost;
	pq.push(a);
	while(!pq.empty()){
		a=pq.top();
		pq.pop();
		if(a.p==n-1 && a.s!=1)return a.cost;
		if(dp[a.p][a.s] < a.cost)continue;
		for(int i=0;i<n;i++){
			if(cost[a.p][i]==INF)continue;
			for(int j=0;j<=1;j++){
				b=Node(i,a.s,a.cost);
				if(a.s==0){
					if(j==0)b.cost += cost[a.p][i];
					else b.s=1;
				}
				else if(a.s==1){
					b.s = 2;
				}
				else if(a.s==2){
					b.cost += cost[a.p][i];
				}
				if(b.cost < dp[b.p][b.s]){
					dp[b.p][b.s] = b.cost;
					pq.push(b);
				}
				if(a.s!=0)break;
			}
		}
	}
}
int main(){
	int n,m;
	while(cin>>n>>m&&(n||m)){
		fill_n((int*)cost,10000,INF);
		while(m--){
			int a,b,c;
			cin>>a>>b>>c;
			a--;b--;
			cost[a][b]=cost[b][a]=c;
		}
		cout<<dijkstra(n)<<endl;
	}
}