#include<iostream>
#include<fstream>
#define inf 1<<30
using namespace std;
int a[2002][2002],n,m,z[100000],K;

ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");

struct muchie
{
	int x,y,c;
}v[100002];

void citire()
{
	f>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(i!=j)
				a[i][j]=inf;
	int contor=0;
	int x;
	while(f>>x)
		z[++contor]=x;
	K=contor-3*m;
	int cnt=0;
	for(int i=K+1;i<=contor-3;i+=3)
	{
		v[++cnt].x=z[i];
		v[cnt].y=z[i+1];
		v[cnt].c=z[i+2];
		a[v[cnt].x][v[cnt].y]=a[v[cnt].y][v[cnt].x]=v[cnt].c;
	}
}

void RF()
{
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				if(a[i][k]!=inf && a[k][j]!=inf)
					if(a[i][j]>a[i][k]+a[k][j])
						a[i][j]=a[i][k]+a[k][j];
}

int main()
{
	citire();
	RF();
	g<<a[1][n];
}