//注意到n 与 m的范围一致，n~m,这代表是稀疏图，若n*n ~ m 代表是稠密图
//稀疏图要用邻接表-堆优化版本的Dijkstra算法，稠密图用邻接矩阵-朴素版本的Dijkstra算法
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> PII;//x 存距起点的离，y存结点的编号

const int N = 150010;

int n, m;
//邻接表四件套+w[N] 每个结点多一个权值，代表边的权值
int h[N],w[N], e[N], ne[N], idx;
int dist[N];//存储每个点到1的距离, 最终答案存储在这。
bool st[N];//已确定了最短路径的点，加入s集合，状态为true,初始化所有的结点都是false

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

int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);// 初始化每个结点到起点1的距离
    dist[1] = 0;//自己到自己的距离为0

    priority_queue<PII, vector<PII>, greater<PII> > heap; //stl建立小根堆,PII x存距离，y存编号，按x排序
    heap.push({0, 1}); // 起点放入堆中，这里为与邻接点那里放入做了铺垫!

    while(heap.size())//当堆不为空,进行下去，有至少n个点且都要放进去，相当于至少迭代了n次，有可能放同样的点
    {
        //每次迭代，找出t<- 在s集合外且距离最短的结点
        auto t = heap.top();//距离最小的结点
        heap.pop();

        int distance = t.first, num = t.second;//t点距离起点最近，编号是num

        if (st[num]) continue;//已经加入s集合的pass
        st[num] = true;//将编号num加入s集合

        //更新其他的结点的距离
        for (int i = h[num]; i != -1; i = ne[i])//遍历num邻接的边，出现重边意味着把同样的点放入堆两次，但st会过滤掉距离大的点，所以不影响
        {
            int j = e[i];// i只是个下标，e中在存的是i这个下标对应的点的编号。
            if (distance + w[i] < dist[j])//t为中间点，令距离更短，更新
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});//其实也可以一开始把所有的点都放进去，那样的时间复杂度会大。
                //这里很巧妙，因为t是求s集合外且距离最短的结点，那每次一定是在邻接的点里找！所以在这里加入堆，数量少准确，堆的操作就会少，时间快
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h); // add之前要初始化邻接表
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);//a -> b ,边权是c。重边不会影响邻接表法的Dijkstra算法,会找到最短路的，自环只会影响负权值的边
    }

    int t = Dijkstra();
    printf("%d\n", t);

    return 0;
}