#include <bits/stdc++.h>
using namespace std;
#define int long long //不开long long见祖宗
const int N=1e6+10;
int n,m,head[N],ne[N],w[N],to[N],id,dis[N],vis[N],cnt[N];
inline void add(int x,int y,int z){
	to[++id]=y,w[id]=z,ne[id]=head[x],head[x]=id;
}
int spfa(){
	memset(dis,-0x3f,sizeof(dis));
	dis[n+1]=0,vis[n+1]=1,cnt[n+1]=1;
	stack<int> q;
	q.push(n+1);
	while(!q.empty()){
		int t=q.top();
		q.pop();
		vis[t]=0;
		for(int i=head[t];i;i=ne[i]){
			int v=to[i];
			if(dis[v]<dis[t]+w[i]){
				dis[v]=dis[t]+w[i];
				if(!vis[v]){
					q.push(v),vis[v]=1;
					if(++cnt[v]>=n) return -1;
				}
			}
		}
	}
	int sum=0;
	for(int i=1;i<=n+1;i++){
		sum+=dis[i];
	}
	return sum;
}
signed main(){
	cin>>n>>m;
	for(int i=0,x,y,z;i<m;i++){
		cin>>z>>x>>y;
		if(z==1){
			add(x,y,0),add(y,x,0);
		}else if(z==2){
			add(x,y,1);
		}else if(z==3){
			add(y,x,0);
		}else if(z==4){
			add(y,x,1);
		}else if(z==5){
			add(x,y,0);		
		} 
	}
	for(int i=1;i<=n;i++) add(n+1,i,1);
	cout<<spfa();
}

/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
LL head[N] , to[N],w[N],ne[N],idx=0;
LL vis[N] , dis[N] ,num[N];
inline void add(int x,int y , int z)
{
	to[++idx] = y;
	w[idx] = z;
	ne[idx] = head[x];
	head[x] = idx;
}
LL n , k;
LL spfa()
{
	memset(dis,-0x3f, sizeof dis);
	stack<int> p;
	dis[n+1] = 0;
	vis[n+1] = 1;
	num[n+1] = 1;
	p.push(n+1);

	while( !p.empty())
	{
		int t = p.top();
		p.pop();
		vis[t] = 0;
		for(int i = head[t] ; i ; i = ne[i])
		{
			int u = to[i];
			if(dis[u] < dis[t] + w[i])
			{
				dis[u] = dis[t] + w[i];
				if(!vis[u]) 
				{
					p.push(u);
					vis[u] = 1;
					if(++num[u] >= n) 
						return -1;
				}
			}
		}
	}

	LL sum = 0;
	for(int i = 1 ; i <= n+1 ; i++)
		sum += dis[i];
	return sum;
}
int main()
{
	cin >> n >> k;
	for(int i = 0 ; i < k ; i++)
	{
		int z,x,y;
		scanf("%d%d%d",&z,&x,&y);
		if(z == 1)
			add (x,y,0),add (y,x,0);
		else if ( z == 2)
			add(x,y,1);
		else if( z == 3)
			add(y,x,0);
		else if(z == 4)
			add(y,x,1);
		else if(z ==5)
			add(x,y,0);
	}
	for(int i = 1 ; i <= n ; i++)
		add(n+1,i,1);
	cout << spfa() << endl;
	return 0;
}

/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
LL head[N] , to[N],w[N],ne[N],idx=0;
LL vis[N] , dis[N] ,num[N];
inline void add(int x,int y , int z)
{
	to[++idx] = y;
	w[idx] = z;
	ne[idx] = head[x];
	head[x] = idx;
}
LL n , k;
LL spfa()
{
	memset(dis,-0x3f, sizeof dis);
	stack<int> p;
	dis[n+1] = 0;
	vis[n+1] = 1;
	num[n+1] = 1;
	p.push(n+1);
	while( !p.empty())
	{
		int t = p.top();
		p.pop();
		vis[t] = 0;
		for(int i = head[t] ; i ; i = ne[i])
		{
			int u = to[i];
			if(dis[u] < dis[t] + w[i])
			{
				dis[u] = dis[t] + w[i];
				if(!vis[u]) 
				{
					p.push(u);
					vis[u] = 1;
					if(++num[u] >= n) 
						return -1;
				}
			}
		}
	}
	LL sum = 0;
	for(int i = 1 ; i <= n ; i++)
		sum += dis[i];
	return sum;
}
int main()
{
	cin >> n >> k;
	for(int i = 0 ; i < k ; i++)
	{
		int z,x,y;
		scanf("%d%d%d",&z,&x,&y);
		if(z == 1)
			add (x,y,0),add (y,x,0);
		else if ( z == 2)
			add(x,y,1);
		else if( z == 3)
			add(y,x,0);
		else if(z == 4)
			add(y,x,1);
		else if(z ==5)
			add(x,y,0);
	}
	for(int i = 1 ; i <= n ; i++)
		add(n+1,i,1);
	cout << spfa() << endl;
	return 0;
}