#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
long long read(){
	long long ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
	 	c=getchar();
	}
	while(c>='0'&&c<='9'){
	 	ans=ans*10+c-'0';
	 	c=getchar();
	}
	return ans*f;
}
long long n,m,t;
struct node{
	int to,next;
	int frd;
}e[maxn*2];
int head[maxn],k=0,du[maxn];
void add(int x,int y,int z){
	du[y]++;
	e[++k].next=head[x];
	e[k].to=y;
	e[k].frd=z;
	head[x]=k;
}
long long ans=0,bk[maxn],fk[maxn];
struct nde{
	long long id,num;
};
queue<nde>q;
int main(){
	n=read();m=read();
	long long a,b,c;
	for(int i=1;i<=m;i++){
		a=read();b=read();c=read();
		add(b,a,c);
		add(c,a,b);
	}
	for(int j=1;j<=n;j++){
		if(du[j]) continue;
		nde tmp;
		tmp.id=j;
		tmp.num=1;
		bk[j]=1;
		q.push(tmp);
		while(!q.empty()){
			tmp=q.front();
			q.pop();
			ans+=tmp.num;
			for(int i=head[tmp.id];i;i=e[i].next){
				int tp=e[i].to;
				bk[tp]=max(bk[tp],tmp.num+bk[e[i].frd]);
				du[tp]--;
				if(du[tp]==0){
					//printf("%d*",bk[tp]);
					nde pmt;
					pmt.id=tp;
					pmt.num=bk[tp];
					q.push(pmt);
				}
			}
		}
		if(ans>1000000000ll) break;
	}
	for(int i=1;i<=n;i++){
		if(du[i]) ans=-1;
	}
	if(ans>1000000000ll) ans=-1;
	printf("%lld",ans);
	return 0;
}