#include <stdio.h>
#define  N  1000
int  num[1002][1002];
int main()
{
    int  i,j,u,mid,m,n,dist[1002],s[1002],path[1002],a,b,c,count;
    scanf ("%d%d",&m,&n);
          for (i=0;i<1002;i++)
             for (j=0;j<1002;j++)
             {
                 if (i!=j)
                    num[i][j]=N;
                 else
                    num[i][j]=0;
             }
          for (i=1;i<=m;i++)
          {
              scanf ("%d%d%d",&a,&b,&c);
              if (c<num[a][b])
              {
                   num[a][b]=c;
                   num[b][a]=c;
              }
          }
          for (i=1;i<=n;i++)
          {
              dist[i]=num[1][i];
              s[i]=0;
              if (num[1][i]<N)   path[i]=1;
              else                   path[i]=-1;
          }
          s[1]=1;   path[1]=0;
          for (i=1;i<=n;i++)
          {
              mid=N;
              u=-1;
              for (j=1;j<=n;j++)
                   if (s[j]==0 && dist[j]<mid)
                   {
                        u=j;
                        mid=dist[j];
                   }
              s[u]=1;
              for (j=1;j<=n;j++)
                  if (s[j]==0)
                       if (num[u][j]<N && dist[u]+num[u][j]<dist[j])
                       {
                           dist[j]=dist[u]+num[u][j];
                           path[j]=u;
                       }
          }
          count=dist[n];
          printf ("%d\n",count);
    return 0;
}