/*************************************************************************
    > File Name: 2387.cpp
    > Author: xudian
    > Email: xudianc@gmail.com
    > Created Time: 五 12/22 09:22:23 2017
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int mp[maxn][maxn];
bool vis[maxn];
int ans[maxn];
int T, N;
void dijkstra(int st){
	memset(vis, false, sizeof vis);
	ans[1] = 0;
	for (int i = 1; i <= N; ++i){
		int tmp = inf;
		for (int j = 1; j <= N; ++j){
			if (!vis[j] and tmp > ans[j]){
				tmp = ans[st = j];
			}
		}
		vis[st] = true;
		for (int j = 1; j <= N; ++j){
			ans[j] = min(ans[j], ans[st] + mp[st][j]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	while (cin >> T >> N){
		memset(mp, 0x3f, sizeof mp);
		memset(ans, 0x3f, sizeof ans);
		int a,b,dis;
		for (int i = 0; i < T; ++i){
			cin >> a >> b >> dis;
			if (mp[a][b] > dis){
				mp[a][b] = mp[b][a] = dis;
			}
		}
		dijkstra(1);
		cout << ans[N] << endl;
	}
	return 0;
}
