#include <bits/stdc++.h>
using namespace std;
const int N = 1e7+5;
int n, k;

struct Edge {
	int to, next, w;
	Edge() {to = next = w = -1;}
}g[N];

int cnt = 0, head[N], dis[N], inq[N], Neg[N];

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

int spfa(int s) {
	memset(Neg, 0, sizeof Neg);
	memset(inq, 0, sizeof inq);
	for (int i = 1; i <= n + 1; i ++)
		dis[i] = -0x3f3f3f3f;
	Neg[s] = 1;
	
	dis[s] = 0;
	queue<int> Q;
	Q.push(s);
	inq[s] = 1;
	
	while (! Q.empty()) {
		int u = Q.front();
		Q.pop();
		inq[u] = 0;
		Neg[u] ++;
		//printf("0\n");
		if (Neg[u] == n)
			return 1;
		for (int i = head[u]; ~ i; i = g[i].next) {
			int v = g[i].to, w = g[i].w;
			if (dis[u] + w > dis[v]) {
				dis[v] = dis[u] + w;
				
				if (! inq[v]) {
					inq[v] = 1;
					Q.push(v);
				} 
			}
		}
	}
	
	return 0;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= k; i ++) {
		int x, a, b;
		scanf("%d%d%d", &x, &a, &b);
		
		switch(x) {
			case 1: add(a, b, 0), add(b, a, 0); break;
			case 2: add(a, b, 1); break;
			case 3: add(b, a, 0); break;
			case 4: add(b, a, 1); break;
			case 5: add(a, b, 0); break;
		}
		
	}
	
	for (int i = n; i >= 1; i --)
		add(n + 1, i, 0);
	
	if (spfa(n + 1) == 1)
		printf("-1\n");
	else {
		int minn = 0x3f3f3f3f, sum = 0;
		for (int i = 1; i <= n; i ++)
			minn = min(minn, dis[i]), sum += dis[i];
		
		if (minn < 0)
			sum += -minn*n;
		else
			sum -= (minn - 1) * n;
			
		printf("%d\n", sum);
	}
	
	return 0;
}