#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,k,x,a,b,h,t,d,num,head[N],l[N],f[N],ind[N],st[N],low[N],dfn[N],s[N],dis[N];
long long ans;
struct edge{int next,to;bool cost;}g[N<<1];
void add(int u,int v,int w){
	g[++num]=(edge){head[u],v,w};
	head[u]=num;
	if(!l[u])   l[u]=num;
}
void tarjan(int u){
	low[st[++num]=u]=dfn[u]=++d;
	for(int i=head[u];i;i=g[i].next){
		if(g[i].cost)   continue;
		int v=g[i].to;
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(!f[v])  low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		++t;
		do  ++s[f[st[num]]=u];	while(st[num--]!=u);
	}
}
int main(){
	cin>>n>>k;
	ans=n;
	while(k--){
		scanf("%d%d%d",&x,&a,&b);
		switch(x){
			case 1:	add(a,b,0);add(b,a,0);break;
			case 2:	add(a,b,1);break;
			case 3:	add(b,a,0);break;
			case 4:	add(b,a,1);break;
			case 5:	add(a,b,0);
		}
	}
	for(int i=1;i<=n;++i)   add(n+1,i,0);
	tarjan(n+1);
	for(int i=1;i<=n+1;++i){
		a=f[i];
		for(int j=head[i];j;j=g[j].next){
			b=g[j].to=f[g[j].to];
			if(a!=b)    ++ind[b];
			else if(g[j].cost)  return puts("-1"),0;
		}
	}
	for(int i=1;i<=n+1;++i)
		if(i!=f[i])	g[l[i]].next=head[f[i]],head[f[i]]=head[i];
	st[num=1]=n+1;
	while(num){
		++h;
		ans+=dis[a=st[num--]]*s[a];
		for(int i=head[a];i;i=g[i].next){
			b=g[i].to;
			dis[b]=max(dis[b],dis[a]+g[i].cost);
			if(!--ind[b])   st[++num]=b;
		}
	}
	return cout<<(h<t?-1:ans),0;
}