#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> PII; //这是一个二元组，即一个数组可以存两个数 第一个叫 对象.first 第二个叫 对象.second

int n, m;
const int N =1e6 + 10; //注意，因为测试数据足够大，所以N的值非常的大
int h[N], e[N], ne[N], w[N], idx; //数据稀疏用邻接表
int dist[N];

bool st[N];

void add(int a, int b, int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int djikstra(){

    memset(dist, 0x3f, sizeof dist); //初始的距离都初始为无限大
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap; 
/*小根堆，即最小值在前面的堆，详情见CSDN，表示是从小到大的堆，但是只能判断最小值，并将其放在头部位置*/

    heap.push({0, 1}); //函数使用详见https://blog.csdn.net/vagrancy7/article/details/81028080?spm=1001.2014.3001.5506
/*堆的这个二元组进行大小比较的时候是先比较first的数据，所以要把距离放在第一个位置，标号放在第二个位置*/

    while (heap.size()){ //进行遍历,可以通过与dijkstra朴素进行比较来学习

        auto t = heap.top(); //将头放在t上然后进行操作
        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]){ /*经典邻接表的遍历，虽然经典，但是左庆又让我对它有新的认识了，
        每次进行遍历的时候都会遍历一条表，而不是一段，比如1-2, 之后是 1-3, 这是因为add()函数h[a]的值是idx ++,
        不会出现走一遍就断的问题，而是把曾经idx ++加的值再减回去，万岁！*/
            int j = e[i]; //当前元素给变量j

            if (dist[j] > dist[ver] + w[i]){ //对距离进行一个更新，跟朴素dijkstra最后的更新类似

                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
                /*更新之后重新放入堆里，神奇的堆会帮你判断谁是最小的值，并放在根的位置（头），
                因为你的一次邻接表遍历会更新出一个起点（只是一个点）到部分点的所有路径，比如 1-2，1-3，1-4，
                所以需要放进堆里，让堆给你判断最小值，其实也省下了一个循环，万岁！*/
            }
        }
    }

    if (dist[n] ==   0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){

    cin >> n >> m;

    memset (h, -1, sizeof h); //用邻接表一定要把h初始化，不然就死循环了!!!!!!!!!

    for (int i = 0; i < m; i ++){
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }

    cout << djikstra() << endl;
    return 0;
}