如果我用 a-1>=b的形式建边，得到的图就是求最短路满足条件。那么我是否可以求出最短路的最小值后，将每个点的值加上这个最小值+1，使得每个点大于0，这样得到答案呢？但是好像和答案差得有点多...

/// 最短路练习
/// 差分约束 + tarjan(scc缩点)

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

using namespace std;

const int N = 200000;

struct Edge {
    int to, cost;
    Edge (int to, int cost): to(to), cost(cost) {}
};

vector<Edge> G[N], Tree[N];
int dis[N];
vector<int> scc[N];
int dfn[N], low[N], c[N];
int cnt = 1, num = 1;
stack<int> stk; int ins[N];
int ind[N];
int n, m, S;

void tarjan(int x) {  // 只搜0权边，缩点
    dfn[x]= low[x] = num++;
    stk.push(x); ins[x] = 1;
    for (int i = 0; i < G[x].size(); i++) {
        Edge e = G[x][i];
        if (e.cost != 0) continue;
        if (!dfn[e.to]) {
            tarjan(e.to);
            low[x] = min(low[x], low[e.to]);
        }
        else if (ins[e.to]) {
            low[x] = min(low[x], dfn[e.to]);
        }
    }
    if (low[x] == dfn[x]) {
        int z;
        while (true) {
            z = stk.top(); stk.pop();
            scc[cnt].emplace_back(z);
            c[z] = cnt; ins[z] = 0;
            if (z == x) break;
        }
        if (x == 0) S = cnt;
        cnt++;
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) G[0].emplace_back(i, 0);
    for (int i = 1; i <= m; i++) {
        int x, a, b; cin >> x >> a >> b;
        if (x == 1) {
            G[a].emplace_back(b, 0);
            G[b].emplace_back(a, 0);
        }
        else if (x == 2) {
            G[b].emplace_back(a, -1);
        }
        else if (x == 3) {
            G[a].emplace_back(b, 0);
        }
        else if (x == 4) {
            G[a].emplace_back(b, -1);
        }
        else if (x == 5) {
            G[b].emplace_back(a, 0);
        }
    }
    /// spfa 时间复杂度太玄乎了，用 tarjan缩点
    for (int i = 0; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 0; i <= n; i++) {
        for (auto j: G[i]) {
            if (j.cost == -1) {
                if (c[i] == c[j.to]) {
                    cout << -1 << endl;
                    return;
                }
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        for (auto j: G[i]) {
            if (c[i] != c[j.to]) {
                Tree[c[i]].emplace_back(c[j.to], j.cost);
                ind[c[j.to]]++;
            }
        }
    }
    /// 直接拓扑排序判断负
    fill(dis, dis+cnt+10, 2e9);
    int ans = 0, minn = 0;
    queue<int> q;
    for (int i = 1; i < cnt; i++) {
        if (ind[i] == 0) {
            dis[i] = 0;
            q.push(i);
        }
    }
    dis[S] = 0; int count = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        count++;
        for (auto i: Tree[u]) {
            if (dis[i.to] > dis[u]+i.cost) {
                dis[i.to] = dis[u]+i.cost;
                minn = min(minn, dis[i.to]);
//                ans += dis[i.to]*(int)scc[i.to].size();
            }
            ind[i.to]--;
            if (ind[i.to] == 0) q.push(i.to);
        }
    }
    for (int i = 1; i < cnt; i++) {
        ans += dis[i]*(int)scc[i].size();
    }
    if (count != cnt-1) cout << -1 << endl;
    else cout << ans+(-1*minn*n)+n << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}