import std.stdio : writeln;
import std.array;
import std.range;
import std.typecons;
import std.algorithm : max, min;

immutable INF = 1 << 27;
immutable N = 100;
int n, m;
int[ N + 1 ][ N + 1 ] adj;
bool[ N + 1 ][ N + 1 ] two_link;

void init(){
	init_d_cost();
	init_two_link();
}

void init_two_link(){
	for( int i = 1; i <= n ; ++i ){
		for( int j = i + 1; j <= n ; ++j ){
			for( int k = 1; k <= n ; ++k ){
				if( k != i && k != j ){
					if( adj[ i ][ k ] * adj[ k ][ j ] != 0 ){
						two_link[ i ][ j ] = two_link[ j ][ i ] = true;
					}
				}
			}
		}
	}
}

int[ N + 1 ] d_cost;
void init_d_cost(){
	d_cost = repeat( INF ).take( N + 1 ).array;
	
	d_cost[ n ] = 0;
	int e = n;
	bool[ N + 1 ] done;
	while( e > 0 ){
		done[ e ] = true;
		
		for( int i = 1; i <= n; ++i ){
			if( !done[ i ] && adj[ e ][ i ] != 0 ){
				int res = d_cost[ e ] + adj[ e ][ i ];
				if( d_cost[ i ] > res ){
					d_cost[ i ] = res;
				}
			}
		}
		
		int min_ = INF;
		int min_idx = 0;
		for( int i = 1; i <= n; ++i ){
			if( !done[ i ] && min_ < d_cost[ i ] ){
				min_ = d_cost[ i ];
				min_idx = i;
			}
		}
		
		e = min_idx;
	}
}

int ans = INF;
bool[ N + 1 ] s_done;
int[ int ] s_note;
void search( int e, int sum ){
	if( e == n ){
		ans = min( ans, sum );
		return;
	}
	
	if( sum >= ans ){
		return;
	}
	
	if( ( e in s_note ) != null ){
		int res = *( e in s_note );
		if( sum >= res ){
			return;
		}
	}else{
		s_note[ e ] = sum;
	}
	
	s_done[ e ] = true;
	
	for( int i = 1; i <= n; ++i ){
		if( two_link[ e ][ i ] ){
			int res = sum + d_cost[ i ];
			ans = min( ans, res );
		}
	}
	
	for( int i = 1; i <= n; ++i ){
		if( adj[ e ][ i ] > 0 ){
			if( !s_done[ i ] ){
				search( i, sum + adj[ e ][ i ] );
			}
		}
	}
	
	s_done[ e ] = false;
}

void main(){
	while( true ){
		n = next!int;
		m = next!int;
		if( ( n | m ) == 0 ){
			break;
		}
		
		ans = INF;
		adj = adj.init;
		two_link = two_link.init;
		s_done = s_done.init;
		s_note = s_note.init;
		
		foreach( i; m.iota ){
			int a = next!int;
			int b = next!int;
			int c = next!int;
			
			adj[ a ][ b ] = adj[ b ][ a ] = c;
		}
		
		init();
		search( 1, 0 );
		
		ans.writeln;
	}
}


import std.stdio : readln;
import std.conv : to;
import std.string : split, chomp;
import std.traits;
string[] input;
string delim = " ";
T next(T)()
in
{
	assert(hasNext());
}
out
{
	input.popFront;
}
body
{
	return input.front.to!T;
}

bool hasNext(){
	if(input.length > 0){
		return true;
	}
	
	string str = readln;
	if(str.length > 0){
		input ~= str.chomp.split(delim);
		return true;
	}else{
		return false;
	}
}


void dbg(T...)(T vs)
{
	import std.stdio : stderr;
	foreach(v; vs)
		stderr.write(v.to!string ~ " ");
	stderr.write("\n");
}

T clone(T)(T v){
	T v_;
	static if(isInputRange!(T)){
		foreach(ite; v){
			v_ ~= ite.clone;
		}
	}else{
		v_ = v;
	}
	
	return v_;
}