//朴素版Dijkstra算法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int N =510;
//m远远大于n，是稠密图，所以采用邻接矩阵；a[i][j]的值是由i结点指向j结点边的权重；
int a[N][N];
int dist[N];//每个结点到1号结点最短距离
bool state[N];//标记该点最短距离是否被确定
int n,m;
void dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=1;i<n;i++)//n-1次迭代，每次迭代确定一个点到起点最短距离
    {
        int t=-1;
        for(int j=1;j<=n;j++)//寻找并确定最短距离
            if(!state[j]&&(t==-1||dist[j]<dist[t]))
                t=j; 
         state[t]=true;
        for(int k=1;k<=n;k++)
            dist[k]=min(dist[k],dist[t]+a[t][k]);//确定最短距离后dist[n]不会再被更新,不受自环影响；
    }
}
int main()
{
    cin>>n>>m;
    memset(a,0x3f,sizeof a);//边长初始化为正无穷
    while(m--)
    {
      int x,y,z;
      scanf("%d%d%d",&x,&y,&z);
      a[x][y]=min(a[x][y],z);//取最小值应对重边；
    }
    dijkstra();
    if(dist[n]==0x3f3f3f3f)
    puts("-1");//1号点和n号点不连通,否则一定能求出
    else
    printf("%d",dist[n]);
    return 0;
}