#include<fstream>
#include<iostream>
int main()
{
	int t[200][200]={0},i,j,k,n,m,a,b,x,c;
	for(i=0;i<200;i++)
		for(j=0;j<200;j++)
			if(i!=j) t[i][j]=1000;
	fstream f,g;
	f.open("ubuntzei.in",ios::in);
	f>>n>>m>>x;
	for(i=1;i<=m;i++)
	{
		f>>a;
		f>>b;
		f>>c;
		t[a][b]=c;
		t[b][a]=c;
	}
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if((t[i][j]>t[i][k]+t[k][j])&&(t[i][k]!=0)&&(t[k][j]!=0))
					t[i][j]=t[i][k]+t[k][j];
	/*for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(t[i][j]==1000)t[i][j]=-1;
			if(t[i][j]!=-1)cout<<t[i][j]<<' ';
			else cout<<'-'<<' ';
		}
		cout<<'\n';
	}*/
	g.open("ubuntzei.out",ios::out);
	g<<t[1][n];
}