#include<bits/stdc++.h>
using namespace std;
int ans,n,k,num,minn=1e9,x,a,b;
int head[100005],cnt[100005],dis[100005];
bool vis[100005];
queue<int>q;
struct Node{
	int to,next,d;
}edge[3*100005];
void add(int u,int v,int d){
	edge[++num].to=v;
	edge[num].d=d;
	edge[num].next=head[u];
	head[u]=num;
}
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0;
	vis[0]=true;
	cnt[0]=-1;
	q.push(0);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=false;
		for(int i=head[x];i;i=edge[i].next){
			int y=edge[i].to;
			int z=edge[i].d;
			if(dis[x]+z<dis[y]){
				dis[y]=dis[x]+z;
				cnt[y]=cnt[x]+1;
				if(cnt[y]==n){
					return false;
				}
				if(!vis[y]){
					vis[y]=true;
					q.push(y);
				}
			}
		}
	}
	return true;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		add(0,i,0);
	}
	for(int i=1;i<=k;i++){
		cin>>x>>a>>b;
		if(x==1){
			add(a,b,0);
			add(b,a,0);
		}
		else if(x==2){
			add(b,a,-1);
		}
		else if(x==3){
			add(a,b,0);
		}
		else if(x==4){
			add(a,b,-1);
		}
		else{
			add(b,a,0);	
		}
	}
	if(spfa()==false){
		cout<<"-1";
	}
	else{
		for(int i=1;i<=n;i++){
			minn=min(minn,dis[i]);
		}
		if(minn<=0){
			minn=abs(minn)+1;
			for(int i=1;i<=n;i++){
				dis[i]+=minn;
			}
		}
		else if(minn>1){
			minn=minn-1;
			for(int i=1;i<=n;i++){
				dis[i]-=minn;
			}
		}
		for(int i=1;i<=n;i++){
			ans+=dis[i];
		}
		cout<<ans;
	}
	return 0;
}