#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
typedef __int128_t LLL;
#define fi first
#define lb lower_bound
#define se second
#define V vector
#define pb push_back
#define all0(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()

const int INF = 2e9 + 100;
const LL INFLL = 8e18 + 1000;

const int MN = 3e5 + 100;

void solve() {
    int n, m; cin >> n >> m;

    V<V<LL>> dis(n + 1, V<LL>(n + 1, INFLL / 2));
    for(int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        dis[a][b] = min(dis[a][b], (LL)c);
    }

    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }


    LL ans = 1e18;
    for(int i = 1; i <= n; i++) ans = min(ans, dis[i][i]);



    if(ans >= 1e17) {
        cout << -1 << endl;
    } else cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) solve();
}