#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,m,h[N],b[N*2],v[N*2],nx[N*2],tt,dfn[N],low[N],sjc,cnt,zhan[N],top,c[N],flz[N],dis[N];
bool pd[N];
int hc[N],bc[2*N],nc[2*N],vc[2*N],tc,rd[N];
long long ans;
void zj(int x,int y,int z)
{
	b[++tt]=y;
	v[tt]=z;
	nx[tt]=h[x];
	h[x]=tt;
}
void sdzj(int x,int y,int z)
{
	bc[++tc]=y;
	vc[tc]=z;
	nc[tc]=hc[x];
	hc[x]=tc;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++sjc;
	pd[x]=true;zhan[++top]=x;
	for(int i=h[x];i;i=nx[i])
	{
		int y=b[i],z=v[i];
		if(z!=0)
		continue;
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(pd[y])
		low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		++cnt;
		int z;
		do
		{
			z=zhan[top--];
			pd[z]=false;
			c[z]=cnt;
			++flz[cnt];
		}while(x!=z);
	}
}
void tp()
{
	int shu=0;
	queue<int> q;
	q.push(0);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=hc[x];i;i=nc[i])
		{
			int y=bc[i],z=vc[i];
			dis[y]=max(dis[x]+z,dis[y]);
			if(--rd[y]==-1)
			q.push(y),++shu;
		}
	}
	for(int i=1;i<=cnt;i++)
	ans+=flz[i]*dis[i];
	if(shu<cnt)
	ans=-1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int typ,x,y;
		scanf("%d%d%d",&typ,&x,&y);
		switch(typ)
		{
			case 1:
				zj(x,y,0);
				zj(y,x,0);
				break;
			case 2:
				zj(x,y,1);
				break;
			case 3:
				zj(y,x,0);
				break;
			case 4:
				zj(y,x,1);
				break;
			case 5:
				zj(x,y,0);
				break; 
		}	
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])
	tarjan(i);
	for(int x=1;x<=n;x++)
	for(int i=h[x];i;i=nx[i])
	{
		int y=b[i],z=v[i];
		if(z==1)
		{
			if(c[x]==c[y])
			{printf("-1");return 0;}
			else
			sdzj(c[x],c[y],1),++rd[c[y]];
		}
		else if(c[x]!=c[y])
		{
			sdzj(c[x],c[y],0);
			++rd[c[y]];
		}
	}
	for(int i=1;i<=cnt;i++)
	sdzj(0,i,1);
	tp();
	printf("%d",ans);
	return 0;
}