SPFA 做法，Bellman-Ford 做法见：https://oj.33dai.cn/p/P1993/solution

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
const int INF = 2147483647;
int n, m;
vector<pair<int, int>> e[MAXN + 1 + 5];
queue<int> q;
int dis[MAXN + 1 + 5];
bool inQ[MAXN + 1 + 5]; // 当前是否在队列里
int cnt[MAXN + 1 + 5];  // SPFA 入队次数
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int c, cc, y;
        cin >> c >> cc >> y;
        e[cc].push_back(make_pair(c, y));
    }
    // 建立超级源点
    int S = n + 1;
    for (int i = 1; i <= n; i++)
        e[S].push_back(make_pair(i, 0));
    // SPFA
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    q.push(S);
    dis[S] = 0;
    cnt[S] = 1;
    inQ[S] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inQ[u] = false;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                if (!inQ[v])
                {
                    q.push(v);
                    cnt[v]++;
                    inQ[v] = true;
                    if (cnt[v] == n)
                    {
                        cout << "NO";
                        return 0;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dis[i] << " ";
    return 0;
}