> #include <iostream>
> #include <stdio.h>
> using namespace std;
> 
> int adjList[1010][1010];
> int adjDist[1010][1010];
> 
> int main() {
> 	int T, N;
> 	scanf("%d%d", &T, &N);
> 	int adjNum[1010] = {0};
> 	for(int i = 0; i < T; i++){
> 		int f, t, d;
> 		scanf("%d%d%d", &f, &t, &d);
> 		if(f == t) continue;
> 		adjList[f][adjNum[f]] = t;
> 		adjDist[f][adjNum[f]] = d;
> 		adjNum[f]++;
> 		adjList[t][adjNum[t]] = f;
> 		adjDist[t][adjNum[t]] = d;
> 		adjNum[t]++;
> 	}
> 	int dist[1010];
> 	int Dist[1010];
> 	bool used[1010] = {0};
> 	used[1] = 1;
> 	dist[1] = 0;
> 	Dist[1] = 0;
> 	for(int i = 2; i <= N; i++) dist[i] = 2147483647;
> 	int added = 1;
> 	while(1){
> 		for(int i = 0; i < adjNum[added]; i++){
> 			if(used[adjList[added][i]]) continue;
> 			if(dist[added] + adjDist[added][i] < dist[adjList[added][i]]){
> 				dist[adjList[added][i]] = dist[added] + adjDist[added][i];
> 			}
> 		}
> 		int mn = 2147483647;
> 		int arg = -1;
> 		for(int i = 2; i <= N; i++){
> 			if(!used[i] && dist[i] < mn){
> 				mn = dist[i];
> 				arg = i;
> 			}
> 		}
> 		used[arg] = 1;
> 		Dist[arg] = dist[arg];
> 		added = arg;
> 		if(arg == N){
> 			break;
> 		}
> 	}
> 	printf("%d\n", Dist[N]);
> 	return 0;
> }