#include<bits/stdc++.h>
#define N 500005
#define inf -1000000000000007
#define int long long
using namespace std;
int n,m,s,dis[N],inq[N],cnt[N];
struct node{
	int to,val;
};
vector<node>g[N];
deque<node>q;
void spfa()
{
	for(int i=1;i<=n;i++)
	dis[i]=inf;
	q.push_back({s,0});inq[s]=1;
	while(q.size())
	{
		int u=q.front().to;
		q.pop_front();inq[u]=0;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].to,w=g[u][i].val;
			if(dis[u]+w>dis[v])
			{
				dis[v]=dis[u]+w;
				cnt[v]++;
				if(cnt[v]>=n){
					cout<<"-1";
					exit(0);
				}
				if(!inq[v]){
					inq[v]=1;
					if(q.size()>=1&&dis[v]>dis[q.front().to]) q.push_front({v,dis[v]});
					else q.push_back({v,dis[v]});
				}
			}
		}
	}
}
signed main()
{
	freopen("1.txt","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int op,x,y;
		scanf("%lld%lld%lld",&op,&x,&y);
		if(op==1){
			g[x].push_back({y,0});
			g[y].push_back({x,0});
		}
		if(op==2)g[x].push_back({y,1});
		if(op==3)g[y].push_back({x,0});
		if(op==4)g[y].push_back({x,1});
		if(op==5)g[x].push_back({y,0});
	}
	s=n+1;
	for(int i=1;i<=n;i++)
	g[s].push_back({i,0});
	spfa();//最长路
	int ans=0;
	for(int i=1;i<=n;i++)
	ans+=dis[i];
	cout<<ans+n;
	return 0;
}