#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void solve()
{
    int n,m;
    scanf("%d%d",&n,&m);
    vector<int> out[n+1],in[n+1];
    int out_cnt[n+1],in_cnt[n+1];
    memset(out_cnt,0,sizeof(out_cnt));
    memset(in_cnt,0,sizeof(in_cnt));
    vector<tuple<int,int,int>> query;
    map<pii,int> mp;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        query.push_back({x,y,z});
//        if(mp[{x,y}]==0)
//        {
            mp[{x,y}]=1;
            out[x].push_back(y);
            out_cnt[x]++;
            in[y].push_back(x);
            in_cnt[y]++;
//        }
//        if(mp[{x,z}]==0)
//        {
            mp[{x,z}]=1;
            out[x].push_back(z);
            out_cnt[x]++;
            in[z].push_back(x);
            in_cnt[z]++;
//        }
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(in_cnt[i]==0)
        {
            q.push(i);
        }
    }
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int y:out[x])
        {
            in_cnt[y]--;
            if(in_cnt[y]==0)
            {
                q.push(y);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(in_cnt[i]>0)
        {
            printf("-1\n");
            return ;
        }
    }
    auto cmp=[&](tuple <int,int,int> a,tuple <int,int,int> b)
    {
        tuple<int,int,int> x,y;
        x={out_cnt[get<0>(a)],out_cnt[get<1>(a)],out_cnt[get<2>(a)]};
        y={out_cnt[get<0>(b)],out_cnt[get<1>(b)],out_cnt[get<2>(b)]};
        return x<y;
    };
    sort(query.begin(),query.end(),cmp);
    ll ans=0;
    ll value[n+1];
    memset(value,0,sizeof(value));
    for(int i=1;i<=n;i++)
    {
        if(out_cnt[i]==0)
        {
            value[i] = 1;
            ans+=value[i];
            if(ans>1e9)
            {
                printf("-1\n");
                return ;
            }
        }
    }
    for(int i=0;i<m;i++)
    {
        int x,y,z;
//        printf("%d %d %d\n",get<0>(query[i]),get<1>(query[i]),get<2>(query[i]));
        tie(x,y,z)=query[i];
        ans-=value[x];
        value[x]=max(value[x],value[y]+value[z]);
        ans+=value[x];
        if(ans>1e9)
        {
            printf("-1\n");
            return ;
        }
//        printf("so I change the value of %d to %lld\n",x,value[x]);
    }
//    ll ans=0;
//    for(int i=1;i<=n;i++)
//    {
////        printf("%lld ",value[i]);
//        ans+=value[i];
//    }
//    printf("\n");
    if(ans>1e9)
    {
        printf("-1\n");
    }
    else
    {
        printf("%lld\n",ans);
    }
}

int main()
{
    int T=1;
    //scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}