#include<iostream>
#include<queue>
#include<cstring>
#define N 2000
int tot=0,head[N],d[N],n,m,x,y,z;
bool vis[N];
using namespace std;
struct edge{
	int u,v,w,next;
}e[N];
struct node{
	int id,d;
	bool operator<(const node x)const{
		return d>x.d;
	}
};
priority_queue<node> q;
bool add_edge(int x,int y,int z){
	tot++;
	e[tot].u=x,e[tot].v=y,e[tot].w=z;
	e[tot].next=head[x];
	head[x]=tot;
}
bool dj(int s){
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[s]=0;
	q.push((node){s,d[s]});
	while(!q.empty()){
		int x=q.top().id;
		q.pop();
		if(vis[x])continue;
		vis[x]=true;
		for(int i=head[x];i;i=e[i].next){
			int w=e[i].w,v=e[i].v;
			if(d[v]>d[x]+w){
				d[v]=d[x]+w;
				q.push((node){v,d[v]});
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		if(x==y)continue;
		else {
			add_edge(x,y,z);
			add_edge(y,x,z);
		}
	}
	dj(1);
	if(d[n]!=0X3f)cout<<d[n];
	else cout<<"-1";
}