#include<bits/stdc++.h>
using namespace std;
#define inf 0x8f8f8f
const int maxn=1e5+1;
int n,k;
struct edge
{
	int to;
	int next;
	int value;
}e[maxn];
int head[maxn];
int cnt;
void add(int from,int to,int value)
{
	e[++cnt].to=to;
	e[cnt].next=head[from];
	e[cnt].value=value;
	head[from]=cnt++;
}
int dis[maxn];
bool flag[maxn];
queue<int>q;
int times[maxn];
long long sum;
int plusn;
void init()
{
	for(int i=1;i<=n;i++)
	{
		dis[i]=inf;
	}
}
int main()
{
	memset(head,-1,sizeof(head));
	init();
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		int x,a,b;
		cin>>x>>a>>b;
		if(x==1)
		{
			add(a,b,0);
			add(b,a,0);
		}
		else if(x==2)
		{
			add(a,b,-1);
		}
		else if(x==3)
		{
			add(a,b,0);
		}
		else if(x==4)
		{
			add(b,a,-1);
		}
		else add(b,a,0);
	}
	for(int i=1;i<=n;i++)
	{
		add(0,i,0);
	}
	dis[0]=0;
	flag[0]=true;
	q.push(0);
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		times[now]++;
		if(now!=0&&times[now]>=n+1)
		{
			cout<<-1<<endl;
			return 0;
		}
		else
		{
			for(int i=head[now];i!=-1;i=e[i].next)
			{
				if(dis[now]+e[i].value>dis[e[i].to])
				{
					dis[e[i].to]=dis[now]+e[i].value;
					if(flag[e[i].to]==false)
					{
						flag[e[i].to]=true;
						q.push(e[i].to);
					}
				}
				now=e[i].to;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(dis[i]<0)
		{
			if(plusn<abs(dis[i]))plusn=abs(dis[i]);
		}
		sum+=dis[i];
	}
	sum+=plusn*n;
	cout<<sum<<endl;
	return 0;
}