import std.stdio;
import std.string;
import std.algorithm;
import std.conv;
import std.array;
import std.math;
import std.range;
import std.typecons;


void main()
{
  for(string[] inputs; (inputs = readln.split)[0] != "0";)
	writeln( solve( inputs[0].to!int, inputs[1].to!int ) );
}

int[][] G, D;
bool[][][] M;

int solve(int n, int m)
{
  G = new int[][](n, n);
  D = new int[][](n, 2);
  M = new bool[][][](n, n, 2);

  foreach(i; 0..n){
	foreach(j; 0..n){
	  G[i][j] = (i == j ? 0 : int.max / 2);
	  M[i][j][0] = M[i][j][1] = false;
	}

	D[i][0] = D[i][1] = int.max / 2;
  }
  
  foreach(_; 0..m){
	auto inputs = readln.split;

	int a = inputs[0].to!int, b = inputs[1].to!int, c = inputs[2].to!int;

	G[a - 1][b - 1] = c;
	G[b - 1][a - 1] = c;

	M[a - 1][b - 1][0] = true;
	M[b - 1][a - 1][0] = true;
  }

  foreach(i; 0..n)
	foreach(j; 0..n)
	  foreach(k; 0..n)
		if(M[i][k][0] && M[k][j][0])
		  M[i][j][1] = true;

  dfs(n, 0, 1, 0);

  return min(D[n - 1][0], D[n - 1][1]);
}

void dfs(int n, int now, int magic, int cost)
{
  if(D[now][magic] <= cost) return;

  D[now][magic] = cost;
  
  foreach(next; 0..n){
	if(M[now][next][0]) dfs(n, next, magic, cost + G[now][next]);
	if(M[now][next][1] && 0 < magic) dfs(n, next, magic - 1, cost);
  }
}

/*
現在いる場所、そこまでの費用、特別乗車券を使ったかどうかで最小値を更新するDFSをします。
特別乗車券を使えるのはi,jの間にパス2の経路が存在する場合だけなので、それをMに記録していきます。
あるkを選択する時iからk、kからjまでの経路が存在すれば特別乗車券が使えます。
*/

/*
2 1
1 2 5
3 2
1 2 5
2 3 5
6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 5 9
4 6 8
0 0
*/