#include
    
     #include
     
      int map[101][101],dist[101];int vis[101];void init1(int n){    int i,j;    for(i = 1;i <= n;i ++)    {        for(j = 1;j <= n;j ++)        {            map[i][j] = 1 << 30;        }    }    return ;}void init2(int n){    int i;    memset(vis,0,sizeof(vis));    for(i = 1;i <= n;i ++)      dist[i] = map[1][i];    return ;}int main(){    int n,m,i,j,k;    int a,b,w,min,sum;    while(~scanf("%d%d",&n,&m) && (m+n))    {        init1(n);        while(m--)        {            scanf("%d%d%d",&a,&b,&w);            map[b][a] = map[a][b] = w;        }        init2(n);        vis[1] = 1;        for(i = 1;i <= n;i ++)        {            min = 1 << 30;            for(j = 1;j <= n;j ++)            {                if(!vis[j] && min > dist[j])                {                    min = dist[j];                    k = j;                }            }            vis[k] = 1;            for(j = 1;j <= n;j ++)            {                if(!vis[j] && dist[j] > dist[k]+map[k][j])                  dist[j] = dist[k]+map[k][j];            }        }        printf("%d\n",dist[n]);    }    return  0;}