#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define rep(i,a) for( int i = 0; i != (a); ++i )
#define repi(i,a,b) for( int i = (a); i != (b); ++i )
#define all(a) (a).begin(), (a).end()

typedef std::pair<int, int> P;	
const int INF = 1 << 30;

int n, m;
int cost[100][100];
bool used[100];

void dijkstra( std::vector<int> &d, int s )
{
	std::fill( all(d), INF );
	std::fill( used, used+n, false );

	d[s] = 0;

	for( ;; )
	{
		int v = -1;
		rep( u, n )
			if( !used[u] && (v == -1 || d[u] < d[v] ) )
				v = u;

		if( v == -1 )
			break;

		used[v] = true;

		rep( u, n )
			d[u] = std::min( d[u], d[v]+cost[v][u] );
	}
	
	return;
}

int main()
{
	while( scanf( "%d%d", &n, &m ), n|m )
	{
		rep( i, n )
			rep( j, n )
				cost[i][j] = i==j?0:INF;

		rep( i, m )
		{
			int a, b, c;
			scanf( "%d%d%d", &a, &b, &c );
			--a; --b;

			cost[a][b] = cost[b][a] = c;
		}

		std::vector<int> d( n ), rd( n );
		dijkstra( d, 0 );
		dijkstra( rd, n-1 );

		int ans = d[n-1];

		rep( i, n )
		{
			rep( j, n )
			{
				if( i == j )
					continue;

				bool fl = false;
				rep( k, n )
					if( i != k && j != k && cost[i][k] != INF && cost[k][j] != INF )
						fl = true;

				if( !fl )
					continue;

				ans = std::min( ans, d[i]+rd[j] );
			}
		}

		printf( "%d\n", ans );
	}

	return 0;
}