#include <bits/stdc++.h>
using namespace std;


#define INF 0x3f3f3f3f
const int N=505;

// 稠密图 使用邻接矩阵存储
int n,m;
int g[N][N];
int dis[N]; // 从1到点i的距离
bool vis[N];

int dijkstra(){
    memset(dis, 0x3f, sizeof dis);
    dis[1]=0; // 设置到起点的距离为0
    for(int i=0; i<n; ++i){
        // 在1到n中找到当前最短路径
        int t=-1;
        for(int j=1; j<=n; ++j){
            if(!vis[j] && (t==-1 || dis[t]>dis[j]))
                t=j;
        }
        vis[t]=true;
        // 距离更新
        for(int j=1; j<=n; ++j)
            dis[j]=min(dis[j], dis[t]+g[t][j]);
    }
    if(dis[n]==INF) return -1;
    return dis[n];
}


int main(){
    cin>>n>>m;
    memset(g, 0x3f,sizeof g);
    int x, y, w;
    while(m--){
        cin>>x>>y>>w;
        g[x][y]=min(g[x][y], w); // 出现重边, 只取权重最小的边
    }
    cout<<dijkstra()<<endl;
    return 0;
}