#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6+10;
int h[N],e[N],w[N],ne[N],idx;
int d[N];
bool vis[N];
int n,m;
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra(){
memset(d, 0x3f, sizeof d); //初始化原来到所有点的距离都为无穷
d[1]=0; //到源点距离为0
priority_queue<PII,vector<PII>,greater<PII>> heap; //将优先队列初始化为小根堆
heap.push({0,1}); //存放顺序为距离 编号 此处存放顺序不能改变 因为排序是根据 pair.fisrst 排序的
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.second,dis=t.first;
if(vis[ver]) continue; //这个点的最短距离已经确定过
vis[ver]=true; //没有 接下来就要确定ver这个点的最短距离
for(int i=h[ver];i!=-1;i=ne[i]){ //遍历该点的所有邻接边
int j=e[i]; //存放邻接边指向的点
if(d[j]>d[ver]+w[i]) { //如果原来到这个点的距离 比经过ver这个点到其的距离还远的话 就更新到j的最短距离
d[j]=d[ver]+w[i];
heap.push({d[j],j}); //进堆
}
}
}
if(d[n]==0x3f3f3f3f) return -1; //判断是否能到n
return d[n];
}
int main(){
memset(h, -1, sizeof h);
cin>>n>>m;
while (m -- ){
int a,b,c;
cin>>a>>b>>c;
add(a, b, c);
}
cout<<dijkstra()<<endl;
return 0;
}