import java.util.Scanner;

public class POJ_2387 {
	private static final int INF = 400000;
	private static int T, N;
	private static int[][] map;
	private static int[] dis;
	private static boolean[] vis;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		T = in.nextInt();
		N = in.nextInt();
		dis = new int[N + 1];
		vis = new boolean[N + 1];
		map = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			dis[i] = INF;
			for (int j = 1; j <= N; j++) {
				map[i][j] = map[j][i] = INF;
			}
		}
		while (T-- > 0) {
			int s = in.nextInt();
			int e = in.nextInt();
			int w = in.nextInt();
//如果有重边，选择最小的
			if (map[s][e] > w)
				map[s][e] = map[e][s] = w;
		}
		dijkstra(1);
		System.out.println(dis[N]);
		in.close();
	}

	private static void dijkstra(int u) {
		for (int i = 1; i <= N; i++) {
			dis[i] = map[u][i];
		}
		dis[u] = 0;
		vis[u] = true;
		for (int t = 0; t < N; t++) {
			int min = INF;
			int k = 0;
			for (int i = 1; i <= N; i++) {
				if (!vis[i] && dis[i] < min) {
					min = dis[i];
					k = i;
				}
			}
			vis[k] = true;
			for (int i = 1; i <= N; i++) {
				if (!vis[i] && dis[i] > dis[k] + map[k][i])
					dis[i] = dis[k] + map[k][i];
			}
		}
	}

}