// 差分约束 Tarjan+拓扑 O(N+M)
#include<bits/stdc++.h>
using namespace std;

const int N=100010;
vector<pair<int,int>>e[N],ne[N];
int n,k;
int dfn[N],low[N],tim,stk[N],top,scc[N],siz[N],cnt;

void tarjan(int u){
  dfn[u]=low[u]=++tim; stk[++top]=u;
  for(auto [v,w]:e[u]){
    if(!dfn[v]){ //若v尚未访问
      tarjan(v);
      low[u]=min(low[u],low[v]);
    }
    else if(!scc[v]) //若v已访问且未构成SCC
      low[u]=min(low[u],dfn[v]);
  }

  if(low[u]==dfn[u]){ //若u不是SCC的根，则low<dfn
    ++cnt; //缩点的个数
    for(int v=-1;v!=u;){
      v=stk[top--];
      scc[v]=cnt; //缩点的编号
      ++siz[cnt]; //缩点的大小
    }
  }
}
int rd[N],f[N];
void build(){
  for(int u=1;u<=n; u++){
    for(auto [v,w]:e[u]){
      int x=scc[u],y=scc[v]; //缩点的编号
      if(x==y && w==1){ //如果是同一缩点且边权为1
        puts("-1");
        exit(0);
      }
      if(x!=y){ //如果是不同的缩点
        ne[x].push_back({y,w}); //缩点连新边
        rd[y]++; //记录入度
      }
    }
  } 
}
void topo(){
  queue<int>q;
  for(int i=1;i<=cnt; i++)if(!rd[i])q.push(i),f[i]=1;
  while(!q.empty()){
    int u=q.front();q.pop();
    for(auto [v,w]:ne[u]){
      f[v]=max(f[v],f[u]+w); //v点的点权（每点的糖果数）
      if(--rd[v]==0) q.push(v);
    }
  }
}
int main(){
  scanf("%d%d",&n,&k);
  for(int i=1,op,a,b;i<=k; i++){
    scanf("%d%d%d",&op,&a,&b);
    if(op==1) e[a].push_back({b,0}),e[b].push_back({a,0}); //a=b
    else if(op==2) e[a].push_back({b,1}); //a<b
    else if(op==3) e[b].push_back({a,0}); //a>=b
    else if(op==4) e[b].push_back({a,1}); //a>b
    else if(op==5) e[a].push_back({b,0}); //a<=b
  }
  
  for(int i=1;i<=n; i++)if(!dfn[i])tarjan(i);
  build(); //建DAG
  topo();  //拓扑
  long long ans=0;
  for(int i=1;i<=cnt; i++)ans+=1ll*f[i]*siz[i]; //每点的糖果数*缩点大小
  printf("%lld\n",ans);
}

/*
求最少，跑最长，要求约束为：A-B>=D（本题判断环需要用tarjan，否则会超时）
*/
#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 10;
vector<pair<int, int>> G[N];
int d[N], n;
bool v[N];
long long spfa() {
    memset(d, -0x3f, sizeof(d));//因为存在0边，所以这里不能初始为0
    memset(v, 0, sizeof(v));
    queue<int> q; q.push(0); v[0] = 1; d[0] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop(); v[x] = 0;
        for (auto i : G[x]) {
            int y = i.first, w = i.second;
            if (d[y] < d[x] + w) {
                d[y] = d[x] + w;
                if (!v[y]) {
                    q.push(y); v[y] = 1;
                }
            }
        }
    }
    long long ans = 0; for (int i = 1; i <= n; i++) ans += d[i];
    return ans;
}
int tsp, cnt, dfn[N], low[N], scc[N];
stack<int> stk; bool instk[N];
void tarjan(int x) {
    dfn[x] = low[x] = ++tsp;
    stk.push(x); instk[x] = 1;
    for (auto i : G[x]) {
        int y = i.first;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (instk[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        cnt++;
        for (int z = -1; z != x;) {
            z = stk.top(); stk.pop(); instk[z] = 0;
            scc[z] = cnt;
        }
    }
}
int main() {
    int m; scanf("%d%d", &n, &m);
    for (int i = 1, X, A, B; i <= m; i++) {
        scanf("%d%d%d", &X, &A, &B);
        //如果 X=1 ．表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的精果一样多。
        if (X == 1) G[A].push_back({B, 0}), G[B].push_back({A, 0});//B-A>=0,A-B>=0
        //如果 X=2 ，表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。
        if (X == 2) G[A].push_back({B, 1});//B-A>=1
        //如果 X=3 ，表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到 的糖果。
        if (X == 3) G[B].push_back({A, 0});//A-B>=0
        //如果 X=4 ，表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。
        if (X == 4) G[B].push_back({A, 1});//A-B>=1
        //如果 X=5 ，表示第 A 个小朋友分到的糖果必须不多于第 B 个小朋友分到的糖果。
        if (X == 5) G[A].push_back({B, 0});//B-A>=0
    }
    for (int i = 1; i <= n; i++) G[0].push_back({i, 1});//i-0>=1,每个小朋友至少1个

    tsp = cnt = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low));
    memset(instk, 0, sizeof(instk));
    tarjan(0);
    bool flag = 0;
    for (int x = 1; x <= n; x++) for (auto i : G[x]) {
        int y = i.first;
        if (i.second && scc[x] == scc[y]) {
            printf("-1\n"); return 0;
        }
    }
    printf("%lld\n", spfa());
    return 0;
}