#include<bits/stdc++.h>
using namespace std;
const int N=510;
const int INF = 0x3f3f3f3f;//数据最大值，4个3f

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

int dijstria()
{
    memset(dist,INF,sizeof dist);
    dist[1]=0;//dist数组初始化，源点距离为0

    for(int i=0;i<n;++i)//n次迭代
    {
        int t = -1;//t表示每次从未确定的点集中找出dist最小的点，初值为-1表示空集，直接将源点放入确定点集
        //第一次for找出未确定点集dist最小点
        for(int j=1;j<=n;++j)
        {
            if(!st[j] && (t==-1 || dist[t]>dist[j]))
            {
                t = j;
            }
        }

        //该点最短路确定，放入确定点集，容易忘
        st[t] = true;

        //更新dist
        for(int j=1;j<=n;++j)
        {
            dist[j] = min(dist[j] , dist[t] + g[t][j]);
        }
    }

    if(dist[n] == INF) return -1;
    return dist[n];
}

int main()
{
    cin>>n>>m;
    memset(g,INF,sizeof g);//带权图初始化
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);//重边处理，取最小
    }

    cout<<dijstria()<<endl;

    return 0;
}