差分约束模板

//a-b>=wi
//a<=b+wi
//也就是从b+wi
//如果你比这个数要大，也就是要变小，刚好符合图论的规则
#include <bits/stdc++.h>
using namespace std;
const int M=1e4+5;

int h[M],ne[M],e[M],w[M],tot;
void add(int from,int to,int wi) {
    e[++tot]=to;
    w[tot]=wi;
    ne[tot]=h[from];
    h[from]=tot;
}

int in[M],dis[M];
bool vis[M];
int n,m;
bool spfa() {
    queue<int>q;
    memset(dis,0x3f,sizeof(dis));
    dis[0]=0;
    q.push(0);
    while(!q.empty()) {
        int t=q.front();
        q.pop();
        vis[t]=0;
        if(++in[t]>n)return 1;
        for(int i=h[t];i;i=ne[i]) {
            int to=e[i];
            if(dis[to]>dis[t]+w[i]) {
                dis[to]=dis[t]+w[i];
                if(vis[to]==0)vis[to]=1,q.push(to);
            }
        }
    }
    return 0;
}

int main() {
    cin>>n>>m;
    while(m--) {
        int x,y,wi;
        cin>>x>>y>>wi;
        add(y,x,wi);
    }
    if(spfa())return cout<<"NO\n",0;
    for(int i=1;i<=n;i++)add(0,i,0);//没有起点就使用超级起点
    if(spfa())return cout<<"NO\n",0;
    int mn=0x3f3f3f3f;
    for(int i=1;i<=n;i++)mn=min(dis[i],mn);
    for(int i=1;i<=n;i++)cout<<dis[i]-mn<<' ';
    return 0;
}