#include <bits/stdc++.h>

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 dij(){
    memset(dis, 0x3f, sizeof(dis));

    dis[1] = 0;

    for(int i = 0; i < n; i++){
        int t = - 1;
        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]);
    }
    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);
    }
    cout<<dij()<<endl;
    return 0;
}