#include<bits/stdc++.h>
#define ll long long
#define alls(x) x.begin(),x.end()
#define ull unsigned long long
#define lowbit(x) x&-x
#define lc p<<1
#define rc p<<1|1
#define PII pair<int,int>
#define vi vector<int>
#define int long long
using namespace std;
const int mod = 998244353;
const int N = 2e5+10;
int n,m;
int d[N];
void solve()
{
    cin >> n >> m;
    int x,y,z;
    vector<PII>E[N];
    for(int i = 0;i<m;i++){
        cin >> x >> y >> z;
        E[x].push_back({y,z});
        d[y]++,d[z]++;
    }
    vector<int> q;
    for(int i = 0;i < n; i++){
        if(d[i] == 0){
            q.push_back(i);
        }
    }
    for(int i = 0;i < q.size(); i++){
        int x = q[i];
        for(auto [y,z] : E[x]){
            for(auto a : {y,z}){
                if(--d[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] : E[x]){
            a[x] = max(a[x], a[y] + a[w]);
        }
    }
    for(int i = 0 ;i < n ;i++){
        ans += a[i];
    }
    if(ans > 1e9){
        cout << -1 << '\n';
        return;
    }
    cout << ans << '\n';
}
signed main()
{
    cout<<fixed<<setprecision(6);
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1;
//    cin >> _;
    while(_--)solve();
}