#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 1e5 + 5;

int n, m;
int head[MAX_N], tot, new_head[MAX_N], new_tot;
struct Edge { int to, w, nxt; } e[MAX_N], new_e[MAX_N];
int dfn[MAX_N], low[MAX_N], id[MAX_N], scc_cnt, tim, siz[MAX_N];
bool ins[MAX_N];
int deg[MAX_N], dis[MAX_N];
stack<int> sta;
vector<int> scc[MAX_N];

void add(int u, int v, int w) {
    e[++tot].to = v, e[tot].w = w, e[tot].nxt = head[u], head[u] = tot;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    sta.push(u), ins[u] = true;
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        scc_cnt++;
        int v;
        do {
            v = sta.top(); sta.pop();
            ins[v] = false;
            id[v] = scc_cnt, scc[scc_cnt].push_back(v);
            siz[scc_cnt]++;
        } while (u != v);
    }
}

void new_add(int u, int v, int w) {
    new_e[++new_tot].to = v, new_e[new_tot].w = w, new_e[new_tot].nxt = new_head[u], new_head[u] = new_tot;
}

void topsort() {
    queue<int> q;
    for (int i = 1; i <= scc_cnt; i++) {
        if (!deg[i]) {
            dis[i] = 1;
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = new_head[u]; ~i; i = new_e[i].nxt) {
            int v = new_e[i].to, w = new_e[i].w;
            dis[v] = max(dis[v], dis[u] + w);
            --deg[v];
            if (!deg[v]) q.push(v);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(head, -1, sizeof(head));
    memset(new_head, -1, sizeof(new_head));
    cin >> n >> m;
    while (m--) {
        int op, u, v;
        cin >> op >> u >> v;
        if (op == 1) add(u, v, 0), add(v, u, 0);
        else if (op == 2) add(u, v, 1);
        else if (op == 3) add(v, u, 0);
        else if (op == 4) add(v, u, 1);
        else add(u, v, 0);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int u = 1; u <= n; u++) {
        for (int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if (id[u] == id[v] && w > 0) {
                cout << -1 << '\n';
                return 0;
            }
            if (id[u] != id[v]) {
                deg[id[v]]++;
                new_add(id[u], id[v], w);
            }
        }
    }
    topsort();
    int ans = 0;
    for (int i = 1; i <= scc_cnt; i++) ans += dis[i] * siz[i];
    cout << ans << '\n';

    return 0;
}