#include <bits/stdc++.h>
#define int long long
using namespace std;
//最长路
/*
1.a=b
2.a<b
3.a>=b
4.a>b;
5.a<=b;
*/
const int N=1e5+10;
const int K=1e5+10;
int aaa;
struct node{
    int to,len;
};
int pre[N],k,d[N],cnt[N];
int f[N];
int n,m,x,a,b;
queue<int> q;
vector<node> t[N];
int spfa(){
    q.push(0);
    f[0]=true;
    memset(d,-0x3f,sizeof(d));
    d[0]=0;
    cnt[0]=0;
    while(!q.empty()){
        aaa++;
        if(aaa>1e7) break;
        int h=q.front();
        q.pop();
        f[h]=false;
        for(auto i:t[h]){
            int v=i.to;
            int w=i.len;
            if(d[h]+w>d[v]){
                d[v]=d[h]+w;
                cnt[v]=cnt[h]+1;
                if(cnt[v]==n+1) return -1;
                if(!f[v]){
                    q.push(v);
                    f[v]=true;
                }
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res+=d[i];
    }
    return res;
}
signed main()
{
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&x,&a,&b);
        if(x==1) t[a].push_back({b,0}),t[b].push_back({a,0});
        else if(x==2) t[a].push_back({b,1});
        else if(x==3) t[b].push_back({a,0});
        else if(x==4) t[b].push_back({a,1});
        else t[a].push_back({b,0});
    }
    for(int i=1;i<=n;i++){
        t[0].push_back({i,1});
    }
    cout<<spfa();
    return 0;
}