思路是差分约束，超级点是 n+1 ，Hack 全过，但是测试点只能对第一个

求调QwQ

#include "bits/stdc++.h"
using namespace std;
struct node {
    int to, w;
} ;
int t, n, m;
int cnt[105], dis[105];
bool vis[105];
vector <node> g[105];
void init() {
    n = m = 0;
    memset(cnt, 0, sizeof(cnt));
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= 105; i++) 
        g[i].clear();
}
void orign() {
    for (int i = 0; i <= n; i++) 
        g[n + 1].push_back({i, 0});
}
bool SPFA() {
    queue <int> q;
    vis[n + 1] = 0, dis[n + 1] = 0;
    q.push(n + 1);
    while (!q.empty()) {
        int u = q.front();
        vis[u] = 0, q.pop();
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].to, w = g[u][i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    vis[v] = 1, cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n + 2) return 0;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--) {
        init();
        cin >> n >> m;
        orign();
        for (int i = 1; i <= m; i++) {
            int s, t, v;
            cin >> s >> t >> v;
            g[s - 1].push_back({t, v});
            g[t].push_back({s - 1, -v});
        }
        if (SPFA()) cout << "true" << endl;
        else cout << "false" << endl;
    }
    return 0;
}