#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 510;
int graph[N][N];    //从节点i到节点j的距离
int dist[N];        //从初始节点到节点i的距离
bool visited[N];    //当前节点的最短距离有没有确定。
int n,m;

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    //处理n个节点的最短距离。
    for(int i = 1; i <= n; ++i)
    {
        //找未处理的，到初始节点距离最短的节点，t == -1 ： 代表还没找到距离最短的点。
        int t = -1; 
        for(int j = 1; j <= n; ++j)
        {
            if(!visited[j] && (t==-1 || dist[t] > dist[j]))
             t = j;
        }

        visited[t] = true; //将节点t加入已经处理过的最短距离的集合中。

        //以节点t的最短距离去更新其他节点的距离，其实就是更新与t邻接的节点，因为不邻接的节点间的距离都是INF。
        for(int j = 1; j <= n; ++j)
        {
            dist[j] = min(dist[j],dist[t]+graph[t][j]);
        }
    }

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

    return dist[n];
}

int main()
{
    cin>>n>>m;
    memset(graph,0x3f,sizeof graph);   //初始化为正无穷，代表两个节点间是不连通的。

    for(int i = 1; i <= m; ++i)
    {
        int a,b,c;
        cin >> a >> b >> c;
        graph[a][b] = min(graph[a][b],c);
    }

    cout << dijkstra()<<endl;

    return 0;
}