> import java.io.*;
> import java.util.*;
> 
> public class Main {
> 	public static void main(String[] args) throws Exception {
> 		int t, n;
> 		int[][] a;
> 
> 		BufferedReader stdin = new BufferedReader(new InputStreamReader(
> 				System.in));
> 		StringTokenizer sz = new StringTokenizer(stdin.readLine());
> 		t=Integer.parseInt(sz.nextToken());
> 		n=Integer.parseInt(sz.nextToken());
> 		
> 		a=new int[n][n];
> 		for(int i=0;i<n;i++){
> 			Arrays.fill(a[i], Integer.MAX_VALUE);
> 		}
> 		for(int i=0;i<n;i++){
> 			a[i][i]=0;
> 		}
> 		
> 		for(int i=0;i<t;i++){
> 			sz=new StringTokenizer(stdin.readLine());
> 			int from=Integer.parseInt(sz.nextToken())-1;
> 			int to=Integer.parseInt(sz.nextToken())-1;
> 			int value=Integer.parseInt(sz.nextToken());
> 			
> 			a[from][to]=a[to][from]=value;
> 		}
> 		
> 		Dijkstra dij=new Dijkstra(n,0);
> 		dij.array=a;
> 		dij.solve();
> 		dij.printLength(n-1);
> 	}
> }
> 
> class Dijkstra {
> 	int n, start;
> 	int[] flag;
> 	int[] cost;
> 	int[] path;
> 	int[][] array;
> 
> 	public Dijkstra(int n, int start) {
> 		this.n = n;
> 		this.start = start;
> 
> 		flag = new int[n];
> 		cost = new int[n];
> 		Arrays.fill(cost, Integer.MAX_VALUE);
> 		path = new int[n];
> 	}
> 
> 	public void solve() {
> 		for (int i = 0; i < n; i++) {
> 			if (array[start][i] != Integer.MAX_VALUE) {
> 				cost[i] = array[start][i];
> 				path[i] = start;
> 			} else
> 				path[i] = -1;
> 		}
> 
> 		cost[start] = 0;
> 		flag[start] = 1;
> 		for (int i = 0; i < n; i++) {
> 			int tmp = Integer.MAX_VALUE, u = 0;
> 			for (int j = 0; j < n; j++) {
> 				if (flag[j] == 0 && cost[j] < tmp) {
> 					tmp = cost[j];
> 					u = j;
> 				}
> 			}
> 
> 			flag[u] = 1;
> 			for (int j = 0; j < n; j++) {
> 				if (flag[j] == 0 && array[u][j] < Integer.MAX_VALUE
> 						&& cost[u] + array[u][j] < cost[j]) {
> 					cost[j] = cost[u] + array[u][j];
> 					path[j] = u;
> 				}
> 			}
> 		}
> 	}
> 
> 	public void printLength(int end) {
> 		System.out.print(cost[end]);
> 	}
> }