#include<bits/stdc++.h>
using namespace std;
struct e{
	long long to;
	long long dis;
	long long nxt;
}edge[502020];
long long head[502020],d[520002],vis[502020],idx,n,m,cnt[502002];
void add(long long from,long long to,long long dis){
	idx++;
	edge[idx].to=to;
	edge[idx].dis=dis;
	edge[idx].nxt=head[from];
	head[from]=idx;
}
/*
1.A=B   A>=B B>=A
2.A<B   B>=A+1
3.A>=B
4.A>B   A>=B+1
5.A<=B  B>=A
6.XI>=1
原点：x0
xi>=x0+1 
*/
bool spfa(){
	stack<long long>q;
	memset(d,-0x3f,sizeof d);
	d[0]=0;
	q.push(0);
	vis[0]=1;
	while(!q.empty()){
		long long h=q.top();
		q.pop();
		vis[h]=0;
		for(long long i=head[h];i;i=edge[i].nxt){
			long long v=edge[i].to;
			if(d[v]<d[h]+edge[i].dis){
				d[v]=d[h]+edge[i].dis;
				cnt[v]=cnt[h]+1;
				if(cnt[v]>=n+1)return 1;
				if(vis[v]==0){
					q.push(v);
					vis[v]=1;
				}
			}
		} 
	}return 0;
}
int main(){
	long long k,a,b,ans;
	cin>>n>>m;
	for(long long i=1;i<=m;i++){
		cin>>k>>a>>b;
		if(k==1){
			add(b,a,0);
			add(a,b,0);
		}else if(k==2)add(a,b,1);
		else if(k==3)add(b,a,0);
		else if(k==4)add(b,a,1);
		else add(a,b,0);
	}
	for(long long i=1;i<=n;i++)add(0,i,1);
	if(spfa())cout<<-1;
	else{
		for(long long i=1;i<=n;i++)ans+=d[i];
		cout<<ans;
	}//一本通AC
}