#include<bits/stdc++.h>
using namespace std;
//std::ios::sync_with_stdio(0);
//std::cin.tie(0);
const int INF=0x3f3f3f3f;
int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF&&n!=0&&m!=0){
    int a[200][200],vis[2000],d[1000];
    memset(a,INF,sizeof(a));
    memset(vis,0,sizeof(vis));
    memset(d,INF,sizeof(d));
    while(m--){
        int x,y,r;
        cin>>x>>y>>r;
        a[x][y]=r;
        a[y][x]=r;
    }
    d[1]=0;
    while(true){
        int k=-1;
        for(int i=1;i<=n;i++)
            if(!vis[i]&&(k==-1||d[i]<d[k])) k=i;
        if(k==-1)break;
        vis[k]=1;
        for(int i=1;i<=n;i++)
            if(!vis[i]&&d[i]>d[k]+a[k][i]) d[i]=d[k]+a[k][i];
    }
    cout<<d[n]<<endl;
    }
}