#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const ll N = 200005;
vector<pii> Adj[N], E[N];
ll dis[N], vis[N];
queue<ll> q;
ll TIME[N];
ll n, m;
ll dfn[N], low[N], t;
bool inst[N];
ll s[N], top;
ll scc, S[N], sz[N];
void tarjan(int x) {
    dfn[x] = low[x] = ++t;
    inst[x] = true;
    s[++top] = x;
    for(auto tmp : Adj[x]) {
        int v = tmp.first, w = tmp.second;
        if (w) continue;
        if (!dfn[v]) {
            tarjan(v);
            low[x] = min(low[v], low[x]);
        } else if (inst[v]) low[x] = min(low[x], dfn[v]);
    }
    if (dfn[x] == low[x]) {
        ++scc;
        while (true) {
            ll h = s[top];
            top--;
            S[h] = scc;
            inst[h] = false;
            sz[scc]++;
            if (h == x) break;
        }
    }
}
bool SPFA() {
    memset(dis, ~0x3f, sizeof(dis)), memset(vis, 0, sizeof(vis));
    dis[0] = 0, vis[0] = 1;
    q = queue<ll>();
    q.push(0);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (auto tmp : E[x]) {
            int v = tmp.first, w = tmp.second;
            if (dis[v] < dis[x] + w) {
                dis[v] = dis[x] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                    TIME[v]++;
                    if (TIME[v] == n + 1) return false;
                }
            }
        }
    }
    return true;
}
map<ll, bool> flag[N];
int f[N];
int main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= m; i++) {
        ll x, a, b;
        scanf("%lld%lld%lld", &x, &a, &b);
        if (x == 1) Adj[a].push_back(make_pair(b, 0)), Adj[b].push_back(make_pair(a, 0));
        else if (x == 2) Adj[a].push_back(make_pair(b, 1));
        else if (x == 3) Adj[b].push_back(make_pair(a, 0));
        else if (x == 4) Adj[b].push_back(make_pair(a, 1));
        else Adj[a].push_back(make_pair(b, 0));
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i++)
        for (auto tmp : Adj[i]) {
            int v = tmp.first, w = tmp.second;
            if (s[i] == s[v]) f[s[v]] += w;
            if (flag[S[i]][S[v]]) continue;
            E[S[i]].push_back(make_pair(S[v], w));
        }
    for (int i = 1; i <= scc; i++)
        if (f[i] < 0) {
            puts("-1\n");
            return 0;
        }
    for (int i = 1; i <= n; i++) E[0].push_back(make_pair(i, 1));
    if (!SPFA()) puts("-1");
    else {
        ll ans = 0;
        for (int i = 1; i <= scc; i++) ans += 1ll * sz[i] * dis[i];
        printf("%lld\n", ans);
    }
    return 0;
}