#include <fstream.h>
int n,m,D[1003][1003],B[1003],v[1003];
void input()
{
	cin >> m >> n;
	int i,a,b,value;
	for(i=1;i<=m;i++){
		cin >> a >> b >> value;
		D[a][b]=value;
		D[b][a]=value;
	}
}
void Dy()
{
	int i,j,min,ch;
	for(i=1;i<=n;i++){
		if(D[n][i]!=0)
			B[i]=D[n][i];
	}
	v[n]=1;
	for(i=2;i<=n;i++){
		min=9999999;
		for(j=1;j<=n;j++){
			if(B[j]!=0 && min>B[j] && v[j]!=1){
				min=B[j];
				ch=j;
			}
		}
		v[ch]=1;
		for(j=1;j<=n;j++){
			if(D[ch][j]!=0 && (B[j]==0 || B[j]>min+D[ch][j])){
				B[j]=min+D[ch][j];
			}
		}
	}
}
void operation()
{
	input();
	Dy();
	cout << B[1] << "\n";
}
int main()
{
	operation();
	return 0;
}