import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {  
    	Scanner jin=new Scanner(System.in);
    	int N,M;
    	int dist[][]=new int[105][105];
    	while((N=jin.nextInt())!=0&&(M=jin.nextInt())!=0){
    		for(int i=1;i<=N;i++)
    			for(int j=1;j<=N;j++)
    				dist[i][j]=i==j?0:10005;
    		for(int i=0;i<M;i++){
    			int A=jin.nextInt(),B=jin.nextInt(),C=jin.nextInt();
    			dist[B][A]=dist[A][B]=Math.min(C,dist[A][B]);
    		}
    		for(int k=1;k<=N;k++)
    			for(int i=1;i<=N;i++)
    				for(int j=1;j<=N;j++)
    					dist[j][i]=dist[i][j]=Math.min(dist[i][j], dist[i][k]+dist[k][j]);
    		System.out.println(dist[1][N]);
    	}
    }
}  
/**************************************************************
	Problem: 2230
	User: admin
	Language: Java
	Result: Accepted
	Time:956 ms
	Memory:57508 kb
****************************************************************/