//郑老师和阿梓一样可爱^_^
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
//#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n,m,cnt[100010],q[100010],h[N],e[3*N],w[3*N],ne[3*N], idx;
long long dist[100010];
bool st[100010];
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa(){
    int hh = 0, tt = 1;
    q[0]=0;
    memset(dist,-0x3f,sizeof dist);
    dist[0]=0;
    st[0]=true;
    while(hh!=tt){
        auto t=q[--tt];
        st[t]=false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1) return true;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
void solve(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    for(int i=1;i<=m;i++){
        int x,a,b;cin>>x>>a>>b;
        if (x == 1) add(b, a, 0), add(a, b, 0);
        else if (x == 2) add(a, b, 1);
        else if (x == 3) add(b, a, 0);
        else if (x == 4) add(b, a, 1);
        else add(a, b, 0);
    }
    for(int i=1;i<=n;i++)add(0,i,1);
    if(spfa())cout<<-1<<endl;
    else{
        long long ans=0;
        for(int i=1;i<=n;i++){
            ans+=dist[i];
        }
        cout<<ans<<endl;
    }
}
signed main(){
    fast
    int t;t=1;//cin>>t;
    while(t--) {
        //run();
        solve();
    }
    return ~~(0^_^0);
}