#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int dist[N];//记录每点离点1的距离 
int a[N][N];//邻接矩阵储存 
bool st[N];//用于判断是否走过，相当于一维的vis 
int n,m;
int Dijkstra(){
    memset(dist,0x3f,sizeof dist);//赋值到最大，以判断是否有路连通 
    dist[1]=0;//到自己是没有距离的 
    for(int i=0;i<n;i++){
        int t=-1;//初值 
        for(int j=1;j<=n;j++){
            if((t==-1||dist[j]<dist[t])&!st[j])//如果是第一条路或路径更短即更新距离 
                t=j;//记录当前最短距离
        }
        st[t]=true;//标记当前路径走过 
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+a[t][j]);//加上当前最短距离 
    }
    if(dist[n]==0x3f3f3f3f  ) return -1;//没有连通的路径 
    return 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(z,a[x][y]);//去重边 
    }
    cout<<Dijkstra()<<"\n";
    return 0;
}//完美结束