#include <bits/stdc++.h>
using namespace std;
struct ff {long long u,v,w;};
long long n,m;
long long sx;
long long dis[100005];
vector<ff> s;
vector<long long> a[100005]; 
bool b[100005];
priority_queue<pair<long long,long long> > ab;
long long fff[3500][3500];
int main()
{
	cin>>n>>m;
	sx=1;
	for(int i=1;i<=m;i++)
	{
		ff e;
		cin>>e.u>>e.v>>e.w;
		if(fff[e.u][e.v]!=0&&fff[e.v][e.u]!=0)
		{
			fff[e.u][e.v]=min(min(e.w,fff[e.u][e.v]),fff[e.v][e.u]);
			fff[e.v][e.u]=fff[e.u][e.v];
		}
		else fff[e.v][e.u]=fff[e.u][e.v]=e.w;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(fff[i][j]!=0) 
			{
				ff e;
				e.u=i;e.v=j;e.w=fff[e.u][e.v];
				s.push_back(e);
			}
		}
	}
	for(int i=0;i<m;i++) a[s[i].u].push_back(i);
	for(int i=1;i<=n;i++) dis[i]=1e9;
	dis[sx]=0;
	ab.push(make_pair(dis[sx],sx));
	while(!ab.empty())
	{
		long long u=ab.top().second;
		ab.pop();
		if(b[u]==1) continue;
		b[u]=1;
		for(int j=0;j<a[u].size();j++)
		{
			long long v=s[a[u][j]].v;
			long long w=s[a[u][j]].w;
			if(b[v]==0&&dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				ab.push(make_pair(-dis[v],v));
			}
		}
	}
	cout<<dis[n];
 	return 0;
}