#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i=0; i<n; i++)
#define INF (1<<20)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

int main()
{
	int n,m;
	int d[110][110], M[110][110];
	while (cin >> n >> m, n) 
	{
		rep(i, n)rep(j, n) { d[i][j] = INF; M[i][j] = 0; };
		rep(i, n)d[i][i] = 0;
		rep(i, m) {
			int a, b, c;
			cin >> a >> b >> c;
			a--, b--;
			d[a][b] = d[b][a] = c;
			M[a][b] = M[b][a] = 1;
		}

		rep(k, n)rep(i, n)rep(j, n)
			d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

		int ans = d[0][n - 1];
		rep(k, n)rep(i, n)rep(j, n)
			if (M[i][k] && M[k][j])ans = min(ans, d[0][i] + d[j][n - 1]);

		cout << ans << endl;
	} 
	return 0;
}