#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using i64=long long;
using u64=unsigned long long;
const int inf=1e9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>>> g(n+1);
    vector<int> in(n+1);
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        in[y]++;
        in[z]++;
        g[x].emplace_back(y,z);
    }
    vector<int> q;
    for(int i=1;i<=n;i++){
        if(in[i]==0) q.push_back(i);
    }
    for(int i=0;i<q.size();i++){
        auto x=q[i];
        for(auto [y,z]:g[x]){
            for(auto p:{y,z}){
                if(--in[p]==0){
                    q.push_back(p);
                }
            }
        }
    }
    if(q.size()!=n){
        cout<<"-1";
        return 0;
    }
    vector<int> a(n+1,1);
    for(int i=n-1;i>=0;i--){
        int x=q[i];
        for(auto [y,z]:g[x]){
            a[x]=max(a[x],a[y]+a[z]);
        }
        if(a[x]>inf){
            cout<<"-1"<<"\n";
            return 0;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=a[i];
    }
    if(ans>inf) ans=-1;
    cout<<ans;
    return 0;
}