#include <cstdio>

#include <cstring>

#define inf 0x3f3f3f3f

#define min(a,b) a<=b?a:b

int vis[], dis[];         //dis[j]表示起点到当前点的最短距离

int n, t;

int map[][];

void dij()

{

    int i, j, cur, k;

    memset(vis, , sizeof(vis));

    for (i = ; i <= n; i++)(i == ) ? (dis[i] = ) : (dis[i] = inf);

    cur = ;

    for (i = ; i < n; i++)      //循环n次，每次挑选没走过的到起点距离最短的点

    {

        vis[cur] = ;

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

        {

            if (vis[j] == )

                dis[j] = min(dis[j], map[cur][j] + dis[cur]);      //更新每个没走过的点，到起点的最短距离

        }

        //选择到起点距离最短的点

        int g = inf; int x = ;

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

        {

            if (dis[j] <= g && !vis[j])

            {

                g = dis[j];

                x = j;

            }

        }

        cur = x;

    }

    printf("%d\n", dis[n]);      //输出终点到起点的最短距离

}

int main()

{

     int i, j, a, b, c;

    while (scanf("%d%d", &t, &n) != EOF)

    {

        memset(map, inf, sizeof(map));

        for (i = ; i <= t; i++)

        {

            scanf("%d%d%d", &a, &b, &c);      //去除重边的情况

            if (c < map[a][b])

                map[a][b] = map[b][a] = c;

        }

        dij();

    }

    return ;

}