/** Dijkstra求最短路II
I: (n, m)有向图；可能重边、自环；边权值为正；
图论经典问题；
O: 1到n的最短路径，不存在则输出-1；
 * IO
 I:
3 3
1 2 2
2 3 1
1 3 4

 O:
3

*/

// 素朴Dijkstra
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

// 邻接表存储有向图：重边不影响最短路，无需插入时保留最小值
int n, m;
int h[N], w[N], e[N], ne[N], idx;
void add(int a, int b, int c)
{
    // idx自己是轴，idx-e对节点一一对应，idx-ne对应轴前面的idx，h初始化-1
    e[idx] = b, ne[idx] = h[a], h[a] = idx;
    w[idx] = c;
    idx ++ ;
}

int dist[N];
int dijkstra()
{
    // dijkstra： 源，距，全，更新
    int goal = 1;

    // ！有些编译器中：大数组充当局部变量会导致运行崩溃
    // int dist[N];
    memset(dist, 0x3f, sizeof dist);
    dist[goal] = 0;

    // ! 全局转局部变量要小心：初始化
    bool find_set[N] = {};

    // 小根堆写法：每次提取权值最小的节点
    // 小根堆实现：STL方式：O(m)=O(n~n^2)
    // 模拟小根堆：能减小维护堆的复杂度O(n)
    // second节点编号，first节点到源点距离
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int node = t.second, distance = t.first;
        // 当前节点还未搜索到
        if (! find_set[node]) 
        {
            find_set[node] = true;
            // 遍历节点每个边：边节点以-1为结尾
            for (int i = h[node]; i != -1; i = ne[i])
            {
                // 选取最小路径：当前点node,通过边idx=i,到达j节点
                int j = e[i];
                if (dist[j] > dist[node] + w[i])
                {
                    dist[j] = dist[node] + w[i];
                    heap.push({dist[j], j});
                }
            }
        }
    }
    // dijkstra输出
    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);
    }

    printf("%d\n", dijkstra());

    return 0;
}