#include<iostream>

#include<stdio.h>

#include<math.h>

#include<vector>

using namespace std;

struct e{

    int next,c;

};

vector<e> edge[];

bool mark[];

int dis[];

int main (){

    int n,m;

    while (cin>>n>>m && n!= && m!=){

        int a,b,c;

        e temp;

        //初始化

        for (int i=;i<=n;i++){

            edge[i].clear();

            dis[i]=-;

            mark[i]=false;

        }

        dis[]=;

        mark[]=true;

        while(m--){

            cin>>a>>b>>c;

            temp.c=c;

            temp.next=a;

            edge[b].push_back(temp);

            temp.next=b;

            edge[a].push_back(temp);

        }

        int newp=;

        for (int i=;i<n;i++){

            for (int j=;j<edge[newp].size();j++){

                int nex=edge[newp][j].next;

                int c = edge[newp][j].c;

                if (mark[nex] == true)

                continue;

                if (dis[nex]==- || dis[nex]>dis[newp]+c)//floyd也有若不可达或者比之小，不知道为啥要有不可达，先记住

                dis[nex] = dis[newp]+c;

            }

            int min=;

            for (int j=;j<=n;j++){

                if (mark[j] == true)

                continue;

                if (dis[j] == -)//因为我们的无穷大不是无穷，而是-1，之后的比大小有影响

                continue;       //所以要加上这个条件

                if(dis[j]<min){

                    min = dis[j];

                    newp=j;

                }

            }

            mark[newp]=true;

        }

    cout<<dis[n]<<endl;

    }

    return ;

}