#include<stdio.h>
#include<string.h>
#define S scanf
#define P printf
#define INF 999999
int map[1001][1001],q[400000],dis[10001],visit[10001];
int n;
void spfa(int s,int m)
{
  int i,k,str=0,end=1;
  q[str] = s;
  dis[s] = 0;
  while(str<end)
  {
    k = q[str];
    visit[k]=0;
    /*for(i=str;i<end;i++)
        P("%d ",q[i]);
    P("\n");*/
    for(i=1;i<=m;i++)
   {
       if(map[k][i]>0 && dis[i] > map[k][i] + dis[k])
       {
            dis[i] = dis[k] + map[k][i];
            if(!visit[i])
            {
                q[end++] = i;
                visit[i] = 1;
            }
       }
    }
    str++;
  }
}
int main()
{
    int i,j,t,tmp1,tmp2,ans,tmp3;
    while(~S("%d%d",&t,&n))
    {
        memset(map,-1,sizeof(map));
        memset(visit,0,sizeof(visit));
        memset(dis,INF,sizeof(dis));
        for(i=0;i<t;i++)
        {
            S("%d%d",&tmp1,&tmp2);
            //tmp3=tmp1>tmp2?tmp1:tmp2;
            //tmp2=tmp1<tmp2?tmp1:tmp2;
            //tmp1=tmp3;
            S("%d",&tmp3);
            if(map[tmp2][tmp1]!=-1)
            {
                map[tmp2][tmp1]=tmp3<map[tmp1][tmp2]?tmp3:map[tmp1][tmp2];
                map[tmp1][tmp2]=map[tmp2][tmp1];
            }
            else
            {
                map[tmp1][tmp2]=tmp3;
                map[tmp2][tmp1]=tmp3;
            }
        }
        dis[1]=0;
        spfa(1,n);
        /*
        for(i=1;i<=n;i++)
         {
            for(j=1;j<=n;j++)
            {
                P("%d ",map[i][j]);
            }
            P("\n");
        }
        for(i=1;i<=n;i++)
            P("%d ",dis[i]);
        P("\n");*/
        P("%d\n",dis[n]);
    }
}
/*
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
*/