#include<iostream>

#include<cstring>

using namespace std;

#define INF 0x3f3f3f3f

int n,m;

int map[][];

int vis[];

int stemp[];

int dijk(){

    memset(vis,,sizeof(vis));

    vis[]=; //标记第一个已选

    memset(stemp,,sizeof(stemp));

    int min;

    int flag1=,countx=,county,index2;

    while(county!=n){//如果是联通图那最先遍历到的就是最小的

        for(int i=;i<=n;i++){//第一重循环寻找可以扩展的点

            if(vis[i]){

                min=INF;

                for(int j=;j<=n;j++){//第二重循环找到该点最短的扩展点

                    if(!vis[j]&&min>map[i][j]){

                        index2=j;

                        min=map[i][j];

                    }

                }

             }

             if(vis[i]&&min+stemp[i]<stemp[countx]+flag1){ //比较每个点的最小扩展点，选出总距离最短的标记该点和对应的扩展点

                flag1=min;

                countx=i;

                county=index2;

             }

        }

//        cout<<"!"<< flag1<<' '<<countx<<' '<<county<<endl;

        map[county][countx]=INF;//一但往前走就不存在回溯

        stemp[county]=flag1+stemp[countx];//记录每一个已选的路程

        vis[county]=;

        flag1=INF;//初始化第一个点满足条件

        countx=;

    }

    return stemp[n];

}

int main(){

    while(cin>>n>>m){

        if(!n&&!m) break;

        memset(map,INF,sizeof(map));

        while(m--){

            int a,b,c;

            cin>>a>>b>>c;

            map[a][b]=c;

            map[b][a]=c;

        }

    cout<<dijk()<<endl;

    }

}