#include<bits/stdc++.h>
using namespace std;
int n,m,s=1,cnt,he[200005],d[200005],bz[200005];
int read_int() 
{
    int x, f = 1;
    char ch;
    while (ch = getchar(), ch < 48 || ch > 57)
        if (ch == '-') f = -f;
    x = ch - 48;
    while (ch = getchar(), ch >= 48 && ch <= 57)
        x = x * 10 + ch - 48;
    return x * f;
}
struct node
{
	int first,second;
};
struct edge{
	int net;
	int to;
	int w;
}e[1000005];
priority_queue<node> q;
void add(int a, int b, int c)
{
	e[++cnt].net=he[a];
	e[cnt].to=b;
	e[cnt].w=c;
	he[a]=cnt;
}
bool operator < (node x, node y)
{
	return x.second > y.second;
}
void dij(int s) {
	memset(d,0x7f/3,sizeof(d));
	d[s]=0; 
	q.push({s,0});
	for(int i=1;i<=n;i++)
	{
		int x=q.top().first; q.pop();
		while(bz[x]) {
			x=q.top().first;
			q.pop();
		} 
		bz[x]=1;
		for(int j=he[x]; j; j=e[j].net)
		{
			if(d[e[j].to]>d[x]+e[j].w) {
				d[e[j].to]=d[x]+e[j].w;
				q.push({e[j].to,d[e[j].to]});
			}
		}
	}
}
int main() {
	n=read_int(),m=read_int();
	int x,y,z;
	for(int i=1;i<=m;i++) {
		x=read_int(),y=read_int(),z=read_int();
		add(x,y,z);
		add(y,x,z);
	}
	dij(s);
	printf("%d",d[n]);
	return 0;
}