#include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define inf 0x3f3f3f3f

 const int maxn = ;

 int vis[maxn], w[maxn][maxn], d[maxn], t, n;

 void Dijkstra()

 {

     for(int i = ; i <= n; i++) d[i] = w[i][n];

     for(int i = ; i <= n; i++)

     {

         int k = -;

         int min1 = inf;

         for(int j = ; j <= n; j++)

         {

             if(vis[j]) continue;

             if(d[j] < min1)

             {

                 min1 = d[j];

                 k = j;

             }

         }

         if(k == -) break;

         vis[k] = ;

         for(int j = ; j <= n; j++)

         {

             if(vis[j]) continue;

             if(d[j] > d[k] + w[k][j] && w[k][j] < inf)

             {

                    d[j] = d[k] + w[k][j];

             }

         }

     }

     return ;

 }

 int main()

 {

     int x, y, len;

     while(~scanf("%d %d", &t, &n))

     {

         for(int i = ; i <= n; i++)

         for(int j = ; j <= n; j++)

         {

             if(i == j) w[i][j] = ;

             else w[i][j] = w[j][i] = inf;

         }

         memset(vis, , sizeof(vis));

         //for(int i = 1; i <= n; i++) d[i] = inf;

         //d[n] = 0;

         while(t-- )

         {

             scanf("%d %d %d", &x, &y, &len);

             //w[x][y] = w[y][x] = len; 刚开始没有进行if判断

             if(w[x][y] > len) w[y][x] = w[x][y] = len;

         }

         Dijkstra();

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

     }

     return ;

 }