#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int>q[200010];
pair<int,int>b[200010];
int vis[200010];
int bj = 1;
int x[200010],y[200010],z[200010];
int dfs(int x) {
    if( !bj )return 0;
    if( q[x].size() == 0 ) {
        b[x].first = 1;
        return 1;
    }
    for(int i = 0;i < q[x].size(); ++i) {
        
        int res;
        if( vis[q[x][i]] ) {
            res = b[q[x][i]].first+b[q[x][i]].second;
            return res;
        }
        vis[q[x][i]] = 1;
        res = dfs(q[x][i]);
        if( res > b[x].first ) {
            b[x].second = b[x].first;
            b[x].first = res;
        }
        else if( res > b[x].second )b[x].second = res;
        if( b[x].first+b[x].second > 1000000000 ) {
            bj = 0;
            return 0;
        }
    }
    return b[x].first+b[x].second;
}
signed main() {
    int n,m;
    cin >> n >>m;
    for(int i = 1;i <= m; ++i) {
        int u,v1,v2;
        cin >> u >> v1 >> v2;
        x[i] = u;
        y[i] = v1;
        z[i] = v2;
        q[u].push_back(v1);
        q[u].push_back(v2);
    }
    int ans = 0;
    for(int i = 1;i <= n; ++i) {
        if( !vis[i] ) {
            vis[i] = 1;
            dfs(i);
        }
    }
    for(int i = 1;i <= n; ++i) {
        ans += b[i].first+b[i].second,bj = min(bj,b[i].first);
        if( b[x[i]].first+b[x[i]].second < b[y[i]].first+b[y[i]].second+ b[z[i]].first+b[z[i]].second ) {
            bj = 0;
            break;
        }
        if( ans > 1000000000 ) {
            bj = 0;
            break;
        }
    }
    if( bj && ans <= 1000000000 )cout << ans <<endl;
    else cout << -1 << endl;
    return 0;
}
// 13 10
// 1 2 3
// 1 3 4
// 2 5 6
// 3 7 8
// 5 10 11
// 6 10 11
// 7 10 11
// 8 10 11
// 4 8 9
// 12 9 13