#include<stdio.h>
#include<fstream.h>
int const pinfinit=36000;
int a[100][100],d[100],s[100],t[100],i,j,n,r,poz,min,k,aux1,aux2;
FILE *f;
FILE *g;

void citire_graf()
{
int x,y,z;
f=fopen("ubuntzei.in","r");
g=fopen("ubuntzei.out","w");
fscanf(f,"%d%d",&n,&k);
fscanf(f,"%d%d",&aux1,&aux2);
for(i=0;i<=n;i++)
	for(j=0;j<=n;j++)
		if(i!=j)
		a[i][j]=pinfinit;
		else
			a[i][j]=0;

for(i=0;i<k;i++)
	{
		fscanf(f,"%d%d%d",&x,&y,&z);
		a[x][y]=z;
		a[y][x]=z;
		
	}

}
void drum(int i)
{
if (t[i]!=0) drum(t[i]);
printf(" %d ",i);
}
int main()
{
citire_graf();
r=1;
s[r]=1;
for(i=1;i<=n;i++)
	{
		d[i]=a[r][i];
		if(i!=r)
			if(d[i]<pinfinit) t[i]=r;
		
	}

for(i=1;i<=n-1;i++)
	{
		min=pinfinit;
		for(j=1;j<=n;j++)
			if(s[j]==0)
				if(d[j]<min)
					{
						min=d[j];
						poz=j;
					}
	s[poz]=1;
	for(j=1;j<=n;j++)
		if(s[j]==0)
			{
				if(d[j]>d[poz]+a[poz][j])
				{
					d[j]=d[poz]+a[poz][j];
					t[j]=poz;
				
				}
			}
	}

fprintf(g,"%d",d[n]);
return 0;
}