#include<bits/stdc++.h>
#define oo 1e18
using namespace std;
typedef long long ll;
struct Point{
	ll num,sum;
};
ll flag=1;
vector<Point>gh[100005];
ll n,m;//未知数，不等式 
ll dis[100005];
ll vis[100005];
ll all[100005];
void SPFA(){
	stack<ll>Q;
	vis[0]=1;
	all[0]=1;
	Q.push(0);
	while(Q.size()){
		ll A=Q.top();
		Q.pop();
		vis[A]=0;
		for(auto p=gh[A].begin();p!=gh[A].end();p++){
			if(dis[(*p).num]<dis[A]+(*p).sum){
				dis[(*p).num]=dis[A]+(*p).sum;
				if(!vis[(*p).num]){
					Q.push((*p).num);
					vis[(*p).num]=1;
				}
			}
		}
		all[A]++;
		if(all[A]>n+1){
			flag=0;
			break;
		}
	}
}
inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while(!(c >= '0' && c <= '9')) {
		if(c == '-')
			f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		x = (x << 1) + (x << 3) + c - '0', c = getchar();
	return x * f;
}

int main(){
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		ll u1,u2,w;
		w=read();
		u1=read();
		u2=read();
		Point t1,t2;
		t1.num=u1;
		t2.num=u2;
		if(w==1){
			t1.sum=0;
			t2.sum=0;
			gh[u1].push_back(t2);
			gh[u2].push_back(t1);
		}
		if(w==2){
			t2.sum=1;
			gh[u1].push_back(t2);
		}
		if(w==3){
			t1.sum=0;
			gh[u2].push_back(t1);
		}
		if(w==4){
			t1.sum=1;
			gh[u2].push_back(t1);
		}
		if(w==5){
			t2.sum=0;
			gh[u1].push_back(t2);
		}
	}
	for(int i=1;i<=n;i++){
		Point temp;
		temp.num=i;
		temp.sum=0;
		gh[0].push_back(temp);
	}
	for(int i=1;i<100005;i++){
		dis[i]=-oo;
	}
	SPFA();
	if(flag){
		ll sum=0;
		ll mi=oo;
		for(int i=1;i<=n;i++){
			sum+=dis[i];
			mi=min(mi,dis[i]);
		}
		if(mi<=0){
			sum+=n;
		}
		cout<<sum;
	}else{
		cout<<-1;
	}
	return 0;
}