#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long inf=2e18;
int n,m;
vector<pair<int,int>>mp[100005];
int f[100005],no[100005];
bool flag[100005];
void spfa(){
	queue<int>q;
	flag[0]=true;
	q.push(0);
	while(!q.empty()){
		int u=q.front();q.pop();
		flag[u]=false;
		for(auto op:mp[u]){
			int v=op.first,w=op.second;
			if(f[v]>w+f[u]){
				f[v]=f[u]+w;
				if(!flag[v]){
					if(no[v]==n){
						cout<<"-1";
						exit(0);
					}
					no[v]++,flag[v]=true;
					q.push(v);
				}
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)mp[0].push_back({i,1});
	for(int i=1;i<=n;i++)f[i]=inf;
	for(int i=1;i<=m;i++){
		int op,u,v;cin>>op>>u>>v;
		if(op==1){//一样多
			mp[u].push_back({v,0});
			mp[v].push_back({u,0});
		}else if(op==2)mp[v].push_back({u,-1});//少于
		else if(op==3)mp[u].push_back({v,0});//不少于
		else if(op==4)mp[u].push_back({v,-1});//多于
		else mp[v].push_back({u,0});//不多于 
	}
	spfa();
	int mn=inf,ans=0;
	for(int i=1;i<=n;i++)mn=min(mn,f[i]);
	for(int i=1;i<=n;i++)ans+=f[i]-mn;
	//for(int i=1;i<=n;i++)cout<<f[i]<<' ';
	cout<<ans+n;
	return 0;
}

不看TLE，只看WA