111111

#include<bits/stdc++.h>
using namespace std;
const int oo=1000000000;
const int M=100005;
int tot,Next[10*M],to[10*M],len[10*M],head[M];
int n,m;
int d[M],mark[M],Q[10*M];
void add(int a,int b,int c)
{
	Next[tot]=head[a],to[tot]=b,len[tot]=c;
	head[a]=tot++;
}
void SPFA(int g)
{
	for(int i=1;i<=n;i++)
	{
		d[i]=oo;mark[i]=0;
	}
	int st=0,ed=0;
	Q[ed++]=g;
	d[g]=0,mark[g]=1;
	while(st<ed)
	{
		int x=Q[st++];
		mark[x]=0;
		for(int i=head[x];i!=-1;i=Next[i])
		{
			int y=to[i],z=len[i];
			if(d[y]>d[x]+z)
			{
				d[y]=d[x]+z;
				if(! mark[y])
				{
					mark[y]=1;
					Q[ed++]=y;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	tot=0;
	for(int i=1;i<=n;i++)
	{
		head[i]=-1;
	}
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c); 
	}
	SPFA(1);
	printf("%d\n",d[n]);
}