#include<iostream>
#include<fstream>
#include<cstring>
#include<stdio.h>
using namespace std;
const int N = 1e3+10;
int g[N][N];//邻接矩阵
int dis[N];//起点到某个点的距离
int st[N];//已确定的点
int n,m;//n个点 m条边
int dijkstra(int u){
memset(dis,0x3f,sizeof dis);//初始距离为无穷
dis[u] = 0;
for(int i = 1;i <= n;i++){//遍历所有的顶点
/**
*Extract-Min操作
*/
int t = -1;//选择下一个顶点
for(int j = 1;j <= n;j++){//找出当前点最短的出边的下一个顶点
if(!st[j] && (t == -1 || dis[j] < dis[t])){//j顶点不在S集合 并且t未确定或者t确定但找到j距离小于t
t = j;
}
}
st[t] = 1;//循环结束后 t也就确定了 将t加入S集合
/**
* Relax操作
* 因为S集合增加了新的点
* 所以更新每个点的最短距离
*/
for(int i = 1;i<=n;i++){//找一个点,如果先到t再到i的距离比原来直接到i更短,就替换该距离
dis[i] = min(dis[i], dis[t] + g[t][i]);
}
}
if(dis[n] > 10000){//说明1无法到达n
return -1;
}
return dis[n];
}
int main(){
memset(g,0x3f,sizeof g);//初始化所有边长均为正无穷
cin>>n>>m;
//因为可能存在重边,所以u到v的重边只要保留最短边即可
int x,y,z;
for(int i = 1;i<=m;i++){
cin>>x>>y>>z;
g[x][y] = min(g[x][y],z);
}
cout<<dijkstra(1);
return 0;
}