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

using namespace std;

const int N = 510;

int n, m;
int g[N][N];    //稀疏图用邻接矩阵
int dist[N];    //每个点到起点的距离数组
bool st[N];     //判断每个点是否被遍历过

int dijkstra()  
{
    memset(dist, 0x3f, sizeof dist);    //初始化距离
    dist[1] = 0;        //初始化起点

    for ( int i = 0; i < n - 1; i ++ )      //进行n - 1次迭代
    {   
        int t = -1;     //设为-1是因为dijkstra适用于无负权边的图
        for ( int j = 1; j <= n; j ++ )     //遍历所有点
            if ( !st[j] && ( t == -1 || dist[t] > dist[j] ) )   //找到未被遍历并且距离起点最近的点
                t = j;      //更新t

        for ( int j = 1; j <= n; j ++ ) 
            dist[j] = min(dist[j], dist[t] + g[t][j]);      //用找到的t来跟新其他所有点

        st[t] = true;   //t用完后标记
    }

    if ( dist[n] == 0x3f3f3f3f ) return -1;     //说明与终点没有通路
    return dist[n];
}

int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    while ( m -- )
    {
        int a, b, w;
        cin  >> a >> b >> w;
        g[a][b] = min(g[a][b], w);      //排除重边
    }

    int t = dijkstra();
    if ( t == -1 ) puts("-1");
    else cout << t << endl;
    return 0;
}