#include<stdio.h>
#include<string.h>
#define MAX 99999999
long v[1005][1005];
int mark[1005];
main()
{
	int n,m;
	while(scanf("%d %d",&n,&m)!=EOF){
		if(n==0&&m==0){
			break;
		}
		int i,j;
		int a,b,c;
		int min;
		int u;
		for(i=1;i<=m;i++){
			for(j=1;j<=m;j++){
				v[i][j]=MAX;
			}
		}
		for(i=1;i<=n;i++){
			scanf("%d %d %d",&a,&b,&c);
			if(v[a][b]>c){
				v[a][b]=v[b][a]=c;
			}
		}
		memset(mark,0,sizeof(mark));
		mark[m]=1;
		for(i=1;i<=m;i++){
			min=MAX;
			for(j=m-1;j>=1;j--){
				if(!mark[j]){
					if(v[j][m]<min){
						min=v[j][m];
						u=j;
					}
				}
			}
			mark[u]=1;
			for(j=m-1;j>=1;j--){
				if(!mark[j]){
					if(v[j][m]>v[j][u]+v[u][m]){
						v[j][m]=v[j][u]+v[u][m];
					}
				}
			}
		}
		printf("%d\n",v[1][m]);
	}
}