#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define int long long
const int N=502024;
typedef pair<int,int> PII;
int n,m,stk[N],nd[N],val[N];
map<int,int> mp[N];
vector<PII> q[N];
vector<int> g[N];
int read(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
signed main()
{
	n=read(); m=read();
	for(int x,y,z,i=1;i<=m;i++){
		x=read(); y=read(); z=read();
		q[x].push_back(make_pair(y,z));
		if(!mp[x][y])mp[x][y]=1,g[y].push_back(x),++nd[x];
		if(!mp[x][z])mp[x][z]=1,g[z].push_back(x),++nd[x];
	}
	int top=0;
	for(int i=1;i<=n;i++)
		if(!nd[i])stk[++top]=i,val[i]=1;
	for(int T=1;T<=top;T++){
		int x=stk[T];
		for(int i=0;i<g[x].size();i++){
			int th=g[x][i];
			if(mp[th][x]){
				mp[th][x]=0,--nd[th];
				if(!nd[th]){
					for(int j=0;j<q[th].size();j++)
						val[th]=max(val[th],val[q[th][j].first]+val[q[th][j].second]);
					if(val[th]>1e9)return puts("-1"),0;
					stk[++top]=th;
				}
			}
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		if(!val[i])puts("-1");
		sum+=val[i];
	}
	if(sum>1e9)puts("-1");
	else printf("%lld\n",sum); 
	return 0;
}