#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
//使用一个堆来维护最短距离, 但是同时还是需要知道节点的编号是多少, 此时使用这种pair的形式来进行存储。
//所以在堆中, 存储的是一个pair,
typedef pair<int, int> PII;
//此时使用的是邻接表来进行边的存储,而邻接表的存储方式相当于使用的是拉链法
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx;
idx ++;
}
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//使用一个优先队列来实现小根堆
priority_queue<PII, vector<PII>, greater<PII>> heap;
//首先应该将1号节点放到堆中, 因为1号节点已经知道最短距离了
//此时将1号点放进去来更新其他可以更新的点。
heap.push({0, 1});
while (heap.size()) {
//首先找到当前距离最小的点
auto t = heap.top();
heap.pop();
//得到此时的点的编号和距离
//此时使用小根堆的时候, 采用的是将距离源点的距离放在的第一个位置,
//因为此时将一个节点放到小根堆中的时候, 此时可以按照第一个位置上的值来进行
//排序, 从而将第一个位置上最小的值放到堆定的位置上。
int ver = t.second, distance = t.first;
//此时因为题目中有存在多重边, 如果此时的这个节点已经得到了最小距离了, 就不需要再来处理了。
//所以此时默认如果是存在有多重边的话, 此时的边上的权值是相等的。
if (st[ver]) continue;
st[ver] = true;
//使用当前的这个点来更新其他点
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
//算法原理就是这样的, 每一次更新完成之后, 都要将这个点放到堆中, 此时
//保证只要有过修改, 就是一定会进入到堆中,此时堆中之前的已经存在的元素也是一定经过了
//连通的路径, 并且是之前在某一次操作过程进行过相应的修改的。
//因为每一次都是要来找到当前局面上的最小值来作为下一次开始的起点。
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}