#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <string>
#include <cmath>
#include <cstdio>
#define FOR(I,A,B) for(int I =(A);I<(B);++I)
#define FORE(I,B) for(int I =1;I<=(B);++I)
#define REP(I,A) FOR(I,0,A)
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
const int INF=1<<30;
using namespace std;
typedef pair<int,int> pr;
typedef tuple<int,int,int> ti;
typedef vector<pr> VP;
typedef vector<VP> VVP;
int DP[300][3];
int main() {
	int n,m,a,b,c;
	
	while(cin>> n >> m && n){
	VVP v(n+1);
	REP(i,300)
		REP(j,3)
			DP[i][j]=INF;
	REP(i,m){
		cin >> a >> b >> c;
		v[a].push_back(pr(c,b));
		v[b].push_back(pr(c,a));
	}
	priority_queue<ti> pq;
	DP[1][0]=0;
	pq.push(ti(0,0,1));
	while(!pq.empty()){
		int c=get<0>(pq.top()),t=get<1>(pq.top()),p=get<2>(pq.top());
		pq.pop();
		if(c!=DP[p][t])
		continue;
		REP(i,v[p].size()){
			int ne=v[p][i].second,co=v[p][i].first;
			if(t%2){
				if(DP[ne][t+1]>c){
					DP[ne][t+1]=c;
					pq.push(ti(DP[ne][t+1],t+1,ne));
				}
			}
			else{
				if(DP[ne][t]>c+co){
					DP[ne][t]=c+co;
					pq.push(ti(DP[ne][t],t,ne));
				}
			}
			if(t==0){
				if(DP[ne][1]>c){
					DP[ne][1]=c;
					pq.push(ti(DP[ne][1],1,ne));	
				}
			}
		}
	}
	cout << min(DP[n][0],DP[n][2]) << endl;
	// your code goes here
	}
	return 0;
}