#include <bits/stdc++.h>
using namespace std;

const int INF = 1e+9;
typedef pair<int, int> P;

struct node {
	int c, to, t;
	node(int c, int to, int t) : c(c), to(to), t(t){}
};

bool operator > (const node& n1, const node& n2){
	return (n1.c == n2.c) ? n1.to > n2.to : n1.c > n2.c;  
}

int N, M;
vector<P> G[101];
int d[101][2];

void dijkstra(int s){
	for(int i = 0; i <= N; ++i){
		d[i][0] = INF;
		d[i][1] = INF;
	}
	priority_queue<node, vector<node>, greater<node>> que;
	que.push(node(0, s, 1));
	d[s][1] = 0;
	while(!que.empty()){
		node n = que.top();
		que.pop();
		if(n.c > d[n.to][n.t])
			continue;
		for(auto& u : G[n.to]){
			if(d[u.first][n.t] > d[n.to][n.t] + u.second){
				d[u.first][n.t] = d[n.to][n.t] + u.second;
				que.push(node(d[u.first][n.t], u.first, n.t));
			}
			if(n.t){
				if(G[u.first].empty())
					continue;
				for(auto w : G[u.first]){
					d[w.first][0] = min(d[w.first][0], d[n.to][1]);
					que.push(node(d[w.first][0], w.first, 0));
				}
			}
		}
	}
}

int main() {
	while(cin >> N >> M && (N || M)){
		for(int i = 0; i <= N; ++i)
			G[i].clear();
		int a, b, c;
		for(int i = 0; i < M; ++i){
			scanf("%d%d%d", &a, &b, &c);
			G[a].push_back(P(b, c));
			G[b].push_back(P(a, c));
		}
		dijkstra(1);
		cout << d[N][0] << endl;
	}
	return 0;
}