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

using namespace std;

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


//总体上就是先找到可以更新的点，之后进行更新。
int disjkstra()
{

    //dist表示的是这个点到起点的最短距离
    memset(dist, 0x3f, sizeof dist);   
    //初始化起点到自己的距离
    dist[1] = 0;   //第一个点，路径为0；

    for(int i=0;i<n-1;i++)    //遍历所有点
    {
         int t = -1;   //储存当前访问的点
         //可以看作一个bool类型
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
            //如果这个点没有被标记and这个点没有被标记为最短路径
            //||发现更短的路径
                t = j;

            for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);
         //找到了距离最小的点t，并用最小的点t去更新其他的点到起点的距离
            st[t]=true;
            //将这个点标记
    }
    if(dist[n]==0x3f3f3f3f)  return -1;   
    //如果这个点与1号点没有路径，那么没有最短路，只能为INF
    return dist[n];
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);

        g[a][b]=min(g[a][b],c);  //去重边，只保留一个
    }
    printf("%d\n",disjkstra());
    return 0;
}