#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define int long long
#define all(v) v.begin(), v.end()
//#define x first
//#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 1e5 + 10;

void solve() {
    int n , m;
    cin >> n >> m;
    vector<vector<PII>> adj(n);
    vector<int> deg(n);
    for(int i = 0 ;i < m ;i ++ ){
        int x,y,z;
        cin >> x >> y >> z;
        x--, y--, z--;
        deg[y]++;
        deg[z]++;
        adj[x].push_back({y,z}); 
    }
    
    vector<int> q;
    for(int i = 0;i < n; i++){
        if(deg[i] == 0){
            q.push_back(i);
        }
    }
    for(int i = 0;i < q.size(); i++){
        int x = q[i];
        for(auto [y,z] : adj[x]){
            for(auto a : {y,z}){
                if(--deg[a] == 0) q.push_back(a);
            }
        }
    }

    if(q.size() != n){
        cout << -1 <<endl;
        return;
    }

    vector<int> a(n,1);
    int ans = 0;
    for(int i = n - 1;i >= 0 ;i--){
        int x= q[i];
        for(auto [y,w] : adj[x]){
            a[x] = max(a[x], a[y] + a[w]);
        }
        // if(a[x] > 1e9){
        //     cout << -1 <<endl;
        //     return;
        // }
    }
    for(int i = 0 ;i < n ;i++){
        ans += a[i];
    }
    if(ans > 1e9){
        cout << -1 << endl;
        return;
    }
    cout << ans << endl;
}
signed main() {
    fastio;
    int T;
 T = 1;
    // cin>>T;
    while (T--) solve();

    return 0;
}