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

using namespace std;

const int N = 501;

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

inline int min(int &a, int &b){return a < b ? a : b;}

int dijkstra(){
    memset(dis, 0x3f,sizeof(dis));
    dis[1] = 0;

    for (int i = 0; i < n; i ++ ){
        int t = -1;
        //更新 t 
        for(int j = 1; j <= n; j++)
          if(!st[j] && (t == -1 || dis[t] > dis[j]))  //当前点更小
             t = j;

        st[t] = true;

        for(int j = 1; j <= n; j++)
          dis[j] = min(dis[j],dis[t] + g[t][j]);   //拿 t 去更新 t 连接的节点
    }
    if(dis[n] == 0x3f3f3f3f) return -1;
    return dis[n];
}


int main(){
    cin >> n >> m;

    memset(g, 0x3f, sizeof(g));

    while (m -- ){
        int a, b , c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b], c);  //重边，取最小的边
    }
    int  t  =  dijkstra();
    cout<< t <<endl;
    return 0;
}