#include<bits/stdc++.h>
using namespace std;
const int maxn = 9000010;
//luogu P3275 [SCOI2011] 糖果
//小点向大点建边 如果会至少大1,边权就为1;

struct node{
	int to,nxt,val;
}e[maxn],ee[maxn];

int dfn[maxn],low[maxn],dfs_clock,sccno[maxn],scc_cnt;
int head[maxn],cnt;
stack<int> S;
int sizep[maxn];
int head1[maxn],cnt1;
int w[maxn],ww[maxn];
int dist[maxn];//存缩完点后每个强连通分量的距离 
long long res;

int n,m;

void add(int u,int v,int c){
	e[++cnt].to = v;
	w[cnt] = c;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}

void add1(int u,int v,int c){
	ee[++cnt1].to = v;
	ww[cnt1] = c;
	ee[cnt1].nxt = head1[u];
	head1[u] = cnt1;
}
void tarjan(int u){
	dfn[u] = low[u] = ++dfs_clock;
	S.push(u);
	for(int i = head[u] ; i ; i = e[i].nxt){
		int v = e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(!sccno[v]){
			low[u] = min(low[u],dfn[v]);
		}
	}
	if(dfn[u] == low[u]){
		scc_cnt++;
		while(true){
			int v = S.top();
			S.pop();
			sccno[v] = scc_cnt;
			sizep[scc_cnt]++;
			if(v == u){
				break;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i++){
		add(0,i,1);
	}
	for(int i = 1 ; i <= m ; i++){
		int a,b,c;
		cin >> c >> a >> b;
		if(c == 1){
			add(a, b, 0);
			add(b, a, 0);
		}
		else if(c == 2){
			add(a, b, 1);
		}
		else if(c == 3){
			add(b, a, 0);
		}
		else if(c == 4){
			add(b, a, 1); 
		}
		else{
			add(a, b, 0);
		}
	}
	tarjan(0);
	bool su = true;
	for(int i = 0 ; i <= scc_cnt ; i++){
		for(int j = head[i] ; j ; j = e[j].nxt){
			int v = e[j].to;
			int a = sccno[i];
			int b = sccno[v]; 
			if(a == b){
				//在同一个连通分量;
				if(w[j] > 0){
					su = false;//存在正环,则无解;
					break; 
				} 
			}
			else{
				add1(a, b, w[j]);
			} 
		}
		if(!su){
			break;
		}
	}
	if(!su){
		cout << -1 << endl;
	}
	else{
		for(int i = scc_cnt ; i ; i--){
			for(int j = head1[i] ; j ; j = ee[j].nxt){
				int v = ee[j].to;
				dist[v] = max(dist[v],dist[i] + ww[j]);
			}
	    }
	    for(int i = 1 ; i <= scc_cnt ; i++){
	    	res += (long long)dist[i] * sizep[i];
	    }
	    cout << res << endl;
	}
	return 0;
}