#include<stdio.h>
#include<string.h>
#define min(a,b) (((a)<(b))?(a):(b))
#define inf 0x3f3f3f3f
int n,m;
int g[105][105];
void floyd() {
    for(int k=1;k<=n;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}
int main() {
    while(1) {
        memset(g,inf,sizeof(g));
        scanf("%d%d",&n,&m);
        if(n==0&&m==0) return 0;
        for(int i=0;i<m;i++) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            g[u][v]=w;
            g[v][u]=w;
        }
        floyd();
        printf("%d\n",g[1][n]);
    }
}