#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
const int MAXN = 3000100;
struct edge
{
	int v,w,nxt;
} e[MAXN];
int head[MAXN],cnt = 0;
int dis[MAXN],du[MAXN];
bool vis[MAXN];
int n,k;
ll ans;
queue<int> q;
void add_edge(int u,int v,int w)
{
	e[++cnt].v = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
void dijkstra(int s)
{

	dis[s] = 0;
	q.push(s);
	vis[s] = true;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v = e[i].v,w = e[i].w;
			if(dis[v] < dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if(!vis[v])
				{
					q.push(v);
					vis[v] = true;
					if(++du[v] == n)
					{
						cout << -1 << endl;
						exit(0);
					}
						
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
		ans += dis[i];
}
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);
		if(a == b && ((x == 2) || (x == 4)))
		{
			cout << -1 << endl;
			return 0;
		}
			
		switch (x) 
		{
			case 1:add_edge(a,b,0);add_edge(b,a,0);break;
			case 2:add_edge(a,b,1);break;
			case 3:add_edge(b,a,0);break;
			case 4:add_edge(b,a,1);break;
			case 5:add_edge(a,b,0);break;
		}
	}
	for(int i=1;i<=n;i++)
		add_edge(0,i,1);
	ans = 0;
	dijkstra(0);
	cout << ans;
	return 0;
}