#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 200005;
vector<int> adj[N];
int ind[N];
ll ans[N];
int main(){ 
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= m;++i){
        int x,y,z;
        cin >> x >> y >> z;
        adj[x].push_back(y);
        adj[x].push_back(z);
        ind[y]++;
        ind[z]++;
    }

    queue<int> q;
    for(int i = 1;i <= n;++i){
        if(!ind[i])q.push(i);
        
    }
    vector<int> tp;

    int t = 1;
    while(q.size()){
        int nn = q.size();
        while(nn--){
            int r = q.front();
            tp.push_back(r);
            q.pop();
            for(int y : adj[r]){
                if(!--ind[y]){
                    q.push(y);
                }
            }
        }
        t++;
    }

    for(int i = 1;i <= n;++i){
        if(ind[i]){
            cout << -1 << '\n';
            return 0;
        }
    }

    for(int i = tp.size() - 1;i >= 0;--i){
        int ii = tp[i];
        if(adj[ii].size() == 0)ans[ii] = 1;
        else{
            ll m1 = 0,m2 = 0;
            for(int y : adj[ii]){
                if(ans[y] > m1){
                    m2 = m1;
                    m1 = ans[y];
                }else if(ans[y] == m1){
                    m2 = ans[y];
                }
            }
            ans[ii] = m1 + m2;
        }
    }
    // for(int i = 1;i <= n;++i){
    //     cerr << ans[i] << ' ';
    // }

    ll sum = 0;
    for(int i = 1;i <= n;++i){
        sum += ans[i];
    }

    cout << (sum > 1e9 ? -1 : sum) << '\n';
    return 0;
}

/*
        o
       / \
      o   o
       \ /
        o

x -> y <=>  x > y

1 2 1 1
*/