#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+5;
const int inf = INT_MAX;
int head[N], cnt1, dis[N], to[N], val[N], nxt[N], cnt[N];
int n, m;
bool vis[N];
void add(int a, int b, int c){
	to[++cnt1] = b;
	val[cnt1] = c;
	nxt[cnt1] = head[a];
	head[a] = cnt1;
}
queue<int> q;
bool spfa(int s){
	for (int i = 1;i <= n;i++) dis[i] = inf;
	//for (int i = 1;i <= n;i++) dis[i] = -inf;
	dis[s] = 0;vis[s] = 1;cnt[s] = 1;q.push(s);
	while (q.size()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for (int i = head[u];i;i = nxt[i]){
			int v = to[i];
			if (dis[v] > (ll)dis[u] + val[i]){
			//if (dis[v] < (ll)dis[u] + val[i])
				dis[v] = dis[u] + val[i];
				if (!vis[v]){
					q.push(v);
					vis[v] = 1;
					++cnt[v];
					if (cnt[v] > n + 1)return 0;
				}
			}
		}
	}
	return 1;
}
int main(){ 
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1;i <= m;i++){
		// a_u - a_v <= w:add(v, u, w)
		int op, u, v;
		cin >> op >> u >> v;
		if (op == 1){
			add(u, v, 0);
			add(v, u, 0);
		}
		else if (op == 2){
			add(v, u, -1);
		}
		else if (op == 3){
			add(u, v, 0);
		}
		else if (op == 4){
			add(u, v, -1);
		}
		else{
			add(v, u, 0);
		}
		//add(u, v, -w);
	}
	for (int i = 1;i <= n;i++) add(0, i, 0);
	if(spfa(0)){
		int mn = 1e9, sum = 0;
		for (int i = 1;i <= n;i++) mn = min(dis[i], mn);
		mn = 0 - mn + 1;
		for (int i = 1;i <= n;i++){
			//printf("%d ", dis[i] + mn);
			sum += dis[i] + mn;
		}
		cout << sum;
	}
	else cout << -1;
	return 0;
}