#include<bits/stdc++.h>
#define int long long
const int N=100005;
int n,k,d[N],vis[N],cnt[N];
struct node
{
	int v,w;
};
std::vector<node> g[N];
bool spfa(int S)
{
	std::queue<int> q;
	q.push(S);
	vis[S]=cnt[S]=1;
	for(int i=1;i<=n;++i)d[i]=0x7fffffff;
	d[S]=0;
	while(q.size())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=0;i<g[u].size();++i)
		{
			int v=g[u][i].v,w=g[u][i].w;
			if(d[u]+w<d[v])
			{
				d[v]=d[u]+w;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
					++cnt[v];
					if(cnt[v]==n)return 0;
				}
			}
		}
	}
	return 1;
}
signed main()
{
//	freopen("P3275_5.in","r",stdin);
	scanf("%lld%lld",&n,&k);
	while(k--)
	{
		int opt,x,y;
		scanf("%lld%lld%lld",&opt,&x,&y);
		if(opt==1)
		{
			g[x].push_back((node){y,0});
			g[y].push_back((node){x,0});
		}
		if(opt==2)
		{
//			B-A>=1 A-B<=-1
			g[y].push_back((node){x,-1});
		}
		if(opt==3)
		{
//			A-B>=0 B-A<=0
			g[x].push_back((node){y,0});
		}
		if(opt==4)
		{
			//A-B>=1 B-A<=-1
			g[x].push_back((node){y,-1});
		}
		if(opt==5)
		{
			//b-a>=0 a-b<=0
			g[y].push_back((node){x,0});
		}
	}
	for(int i=1;i<=n;++i)g[0].push_back((node){i,0});
	if(!spfa(0))return puts("-1")&0;
	int ans=0,x=0;
	for(int i=1;i<=n;++i)if(d[i]<=0)x=std::max(x,-d[i]+1);
	for(int i=1;i<=n;++i)ans+=d[i]+x; 
	printf("%lld",ans);
}