#include<bits/stdc++.h>
using namespace std;
const int N=20010,M=20010;
int e[M],w[M],ne[M],h[N],idx,book[N],dis[N],n,m;
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx;
idx++;
}
void Dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
book[1]=0;
for(int i=1;i<n;i++){
int mind=0x3f3f3f3f,s;
for(int j=1;j<=n;j++){
if(mind>dis[j]&&book[j]==0){
mind=dis[j];
s=j;
}
}
book[s]=1;
for(int j=h[s];j!=-1;j=ne[j]){
dis[e[j]]=min(dis[e[j]],dis[s]+w[j]);
}
}
}
int main(){
memset(h,-1,sizeof(h));
int a,b,c,k;
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
Dijkstra();
if(dis[n]!=0x3f3f3f3f) cout<<dis[n];
else cout<<-1;
return 0;
}
/*
