~

     int s[610],i,j,k,min; int pre[610];

         for(i=0;i<=n;i++){
             d[i]=cost[1][i];
             s[i]=0;
               if(d[i]<max)
                   pre[i]=1;
               else pre[i]=0;

         }


   s[1]=1;
   pre[1]=0;
       for(i=1;i<=n;i++){
        min=max;
        k=0;
        for(j=1;j<=n;j++)
               if(s[j]==0)
                     if(d[i]!=0 && d[i]<min)
                       {
                        min=d[i];
                        k=j;
                        }


        if(k==0) continue;
        s[k]=1;
         for(j=1;j<=n;j++)
              if(s[j]==0 && cost[k][j]<max)
         if(d[k]+cost[k][j]<d[j]){
            d[i]=d[k]+cost[k][i];
            pre[i]=k;


         }


       }

int m,n,x,y,z,i,j;
int d[610];

scanf("%d%d",&m,&m);


   for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
          cost[i][j]=max;


   for(i=1;i<=m;i++){
    scanf("%d%d%d",&x,&y,&z);
       cost[x][y]=z;
       cost[y][x]=z;
       cost[i][i]=0;

   }

   shortsetpath(cost,d,n);


   printf("%d",d[n-1]);