#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int g[N][N], dist[N];
bool st[N];
int n, m;

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//节点到集合的距离定义为正无穷
    dist[1] = 0;

    for(int i = 0; i < n - 1; i ++)//n - 1个点不断加入
    {
        int t = -1;//通过将 t 初始化为 -1，可以确保在开始选择节点之前，不存在已经被选中的节点
        for(int j = 1; j <= n; j ++)
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))// 找到最近的节点
                t = j;
        }

        for(int j = 1; j <= n; j ++)
        {

        }//现在找到t了，遍历一遍所有点，有一下几种情况
        //1.j点和t点之间无连接，那么g[t][j]=0x3f3f3f3f,特别大，会被pass
        //2.dist[j]<=dist[t]+g[t][j],源点到j点的距离，如果经过t后距离更长了，那么不考虑
        //3.dist[j]<=dist[t]+g[t][j],，~~，经过t点距离更短了，那么修改dist[j]的值
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
        st[t] = true;
    }
    if(dist[n] == INF) return -1;//当前点n没被修改，说明到不了点n，输出-1
    return dist[n];
}

int main()
{

    cin >> n >> m;
    memset(g, 0x3f, sizeof g);// 先把每个节点到集合的距离定义为正无穷


    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;

        g[a][b] = min(g[a][b], c);//有效解决多条边的问题，保留最短边， 没有对称性
    }

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