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[] line; (line = readln.split)[0] != "0";)
	writeln( solve( line[0].to!int, line[1].to!int ) );
}

int[][] G, M, D;

int solve(int n, int m)
{
  string[] line;

  G = new int[][](n, n);
  M = new int[][](n, n);
  D = new int[][](n, 2);
  
  foreach(i; 0..n){
	foreach(j; 0..n)
	  G[i][j] = M[i][j] = (i == j ? 0 : int.max / 2);

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

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

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

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

  foreach(i; 0..n) foreach(j; 0..n) foreach(k; 0..n)
	M[i][j] = min(M[i][j], M[i][k] + M[k][j]);

  rec(n, 0, 1, 0);

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

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

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