#include<bits/stdc++.h>
using namespace std;
long long h[200005],w[200005],vis[100005],dis[100005],e[200005],nxt[200005],ct[100005],cnt,n,k,ans=0;
void add(int x,int y,int z)
{
    e[++cnt]=y;
    w[cnt]=z;
    nxt[cnt]=h[x];
    h[x]=cnt;
}
int spfa(int s)
{
    memset(dis,-0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(ct,0,sizeof(ct));
    deque<int> q;
    dis[s]=0;
    vis[s]=1;
    q.push_back(s);
    while(!q.empty())
    {
        int x=q.front();
        vis[x]=0; 
        q.pop_front();
        for(int i=h[x];i;i=nxt[i])
        {
            int j=e[i];
            if(dis[j]<dis[x]+w[i])
            {
                dis[j]=dis[x]+w[i];
                ct[j]=ct[x]+1;
                if(ct[j]>=n+1)return -1;
                if(!vis[j])
                {
                	//cout<<ct[j]<<" "; 
                    vis[j]=1;
                    if(q.size()&&dis[j]<dis[q.front()])q.push_front(j);
                    else q.push_back(j);
                }
            }
        }
    }
    return 0;
}
int main() 
{
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
    	int x,y,z;
        cin>>x>>y>>z;
        if(x==1)
        {
        	add(y,z,0);
        	add(z,y,0);
		}
        if(x==2)add(y,z,1);
        if(x==3)add(z,y,0);
        if(x==4)add(z,y,1);
        if(x==5)add(y,z,0);
    }
    for(int i=1;i<=n;i++)add(0,i,1);
    if(spfa(0)==-1)cout<<-1;
    else
    {
    	for(int i=1;i<=n;i++)
		{
			ans+=dis[i];
			//cout<<dis[i]<<" ";
		}
 	  	cout<<ans;
	}
    return 0;
}