#include<cstdio>

 #include<cstring>

 #define mst(a,b) memset(a,b,sizeof(a))

 #define F(i,a,b) for(int i=a;i<=b;i++)

 const int N=,inf=<<;

 int g[N],v[N*],nxt[N*],w[N*],ed,d[N],in[N],cnt[N],Q[N];

 inline void adg(int x,int y,int z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}

 bool spfa(int S,int n,int hd=,int tl=){//S为源点，n为点数

     F(i,,n)d[i]=inf;

     mst(cnt,),mst(in,),cnt[S]=,Q[++tl]=S,d[S]=;

     for(int x,i;hd<=tl;)for(i=g[x=Q[hd++]],in[x]=;i;i=nxt[i])

         if(d[v[i]]>d[x]+w[i]){

             d[v[i]]=d[x]+w[i];

             if(!in[v[i]]){

                 in[v[i]]=,d[v[i]]<d[Q[hd]]?Q[--hd]=v[i]:Q[++tl]=v[i];//SLF优化

                 if(++cnt[v[i]]>n)return ;//有负环

             }

         }

     return ;

 }

 int n,m;

 int main(){

     while(scanf("%d%d",&n,&m),n+m){

         mst(g,),ed=;

         int x,y,z;

         F(i,,m)scanf("%d%d%d",&x,&y,&z),adg(x,y,z),adg(y,x,z);

         spfa(,n),printf("%d\n",d[n]);

     }

     return ;

 }