rt

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 1e5 + 5;

int n, m, dfn[N], low[N], dfn_cnt, stk[N], tot, in_stk[N];
int sz[N], scc, col[N], inv[N], dp[N];
ll ans;
vector<pii> G[N], g[N];

void Tarjan(int u){
  dfn[u] = low[u] = ++dfn_cnt;
  in_stk[u] = 1, stk[++tot] = u;
  for(const auto &e : G[u]){
  	int v = e.first, w = e.second;
  	if(w) continue;
  	if(!dfn[v]){
  	  Tarjan(v);
	  low[u] = min(low[u], low[v]);		
	}else if(in_stk[v]){
	  low[u] = min(low[u], dfn[v]);
	}
  }
  if(dfn[u] == low[u]){
  	scc++;
  	do{
  	  col[stk[tot]] = scc;
	  sz[scc]++;
	  in_stk[stk[tot]] = 0;	
	}while(stk[tot--] != u);
  }
}

bool Topo(){
  queue<int> q;
  for(int i = 1; i <= scc; i++){
  	if(!inv[i]) q.push(i);
  }
  int cnt = 0;
  for(; !q.empty(); ){
  	int u = q.front(); q.pop();
  	cnt++;
  	for(const auto &e : g[u]){
  	  dp[e.first] = max(dp[e.first], dp[u] + e.second);
	  if(!--inv[e.first]) q.push(e.first);	
	}
  }
  if(cnt != scc) return 0;
  for(int i = 1; i <= scc; i++){
  	ans += sz[i] * dp[i];
  }
  return 1;
}

int main(){
  cin >> n >> m;
  for(int i = 1, op, u, v; i <= m; i++){
  	cin >> op >> u >> v;
  	if(op == 1){
  	  G[u].push_back({v, 0}), G[v].push_back({u, 0});	
	}else if(op == 2){
	  G[v].push_back({u, 1});	
	}else if(op == 3){
      G[u].push_back({v, 0});	
	}else if(op == 4){
	  G[u].push_back({v, 1});
	}else{
	  G[v].push_back({u, 0});
	}
  }
  for(int i = 1; i <= n; i++){
  	if(!dfn[i]) Tarjan(i);
  }
  for(int i = 1; i <= n; i++){
  	for(const auto &e : G[i]){
  	  if(col[i] != col[e.first]){
  	    inv[col[e.first]]++;
		g[col[i]].push_back({col[e.first], e.second});	
	  }	
	}
  }
  cout << (Topo() ? ans : -1);
  return 0;
}