#include<iostream>
#include<algorithm>
#define MAX 1002
using namespace std;
int map[MAX][MAX],d[MAX];
bool flag[MAX];
int n;
int m;
void dijk()
{
	int i,j,xia,min;
	flag[0]=1;
	d[0]=0;	
	while(1)
	{
		xia=-1;
		min=-1;
		for(i=0;i<n;i++)
		{	
			if(flag[i]==1&&d[i]!=-1)
	        for(j=0;j<n;j++)
			{
		        if(flag[j]==0&&map[i][j]!=-1)
				{
				    if(map[i][j]+d[i]<min||min==-1)
					{
						min=map[i][j]+d[i];
				        xia=j;
					}
				}
			}
		}//取出最小边
		if(xia!=-1)
		{
			flag[xia]=1;
	    	d[xia]=min;
		}
        if(xia==-1)break;
	}
}

int main()
{
    int a,b,x;int i,j;
    while(cin>>m>>n)
	{
		for(i=0;i<n-1;i++)
		{
			d[i]=-1;flag[i]=0;
			for(j=i+1;j<n;j++)map[i][j]=map[j][i]=-1;
		}
		d[n-1]=-1;flag[n-1]=0;
		for(i=0;i<m;i++)
		{
			scanf("%d %d %d",&a,&b,&x);
			if(map[a-1][b-1]==-1||map[a-1][b-1]>x)map[a-1][b-1]=map[b-1][a-1]=x;
		}
		dijk();
		cout<<d[n-1]<<endl;
	}
	return 0;
}