#include<bits/stdc++.h>

#define max_v 102000

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

struct edge{int to,cost;};

typedef pair<int,int> P;

int V;

vector<edge>G[max_v];

int d[max_v];

void dijkstra(int s){

    priority_queue<P,vector<P>,greater<P> >que;

    fill(d,d+V+,inf);

    d[s]=;

    que.push(P(,s));

    while(que.size()){

        P p=que.top();

        que.pop();

        int v=p.second;

        if(d[v]<p.first) continue;

        for(int i=;i<G[v].size();i++){

            edge e=G[v][i];

            if(d[e.to]>d[v]+e.cost){

                d[e.to]=d[v]+e.cost;

                que.push(P(d[e.to],e.to));

            }

        }

    }

}

int main(){

    int n,m;

    while(cin>>n>>m&&n||m){

        memset(G,,sizeof G);

        V=n;

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

            int a,b,c;

            cin>>a>>b>>c;

            G[a].push_back((edge){b,c});

            G[b].push_back((edge){a,c});

        }

        dijkstra();

        cout<<d[V]<<endl;

    }

    return ;

}