/kk，大佬帮帮我吧。

#include"iostream"
#include"cstdio"
#include"cmath"
#include"queue"
using namespace std;

#define MAXN 100005

int n,m;
struct node
{
	int to,nxt,w;
}e[MAXN*3];
int head[MAXN],cnt=0;
int t,x,y;
int vis[MAXN],len[MAXN];
queue<int> q;
long long ans=0,dis[MAXN],minx=0x7fffffff;

inline void add(int u,int v,int w)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	e[cnt].w=w;
	head[u]=cnt;
}

inline int read()
{
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0') c=getchar();
	while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return x;
}

inline void SPFA()
{
	vis[0]=1,q.push(0),len[0]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop(),vis[u]=0;
		for(register int i=head[u];i;i=e[i].nxt)
		{
			int j=e[i].to;
			if(dis[j]>dis[u]+e[i].w)
			{
				dis[j]=dis[u]+e[i].w,len[j]=len[u]+1;
				if(len[j]>=n+2){printf("-1\n");return;}
				if(!vis[j]) vis[j]=1,q.push(j);
			}
		}
	}
	for(register int i=1;i<=n;i++) minx=min(minx,dis[i]);
	minx=-minx+1;
	for(register int i=1;i<=n;i++) ans=ans+dis[i]+minx;
	printf("%lld\n",ans);
	return;
}

int main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	n=read(),m=read();
	for(register int i=1;i<=m;i++) 
	{
		t=read(),x=read(),y=read();
		if(t==1) add(x,y,0),add(y,x,0);
		else if(t==2)
		{
			if(x==y) return puts("-1"),0;
			add(y,x,-1);
		}
		else if(t==3) add(x,y,0);
		else if(t==4)
		{
			if(x==y) return puts("-1"),0;
			add(x,y,-1);
		}
		else add(y,x,0);
	}
	for(register int i=1;i<=n;i++) add(0,i,0),dis[i]=1e12;
	SPFA();
	return 0;
}