Solution
首先考虑把答案为 \(-1\) 的点去掉，它们不会影响别的点的答案，这个地方用一个拓扑就可以解决了。
然后对于原图上剩下的边，我们依次将他们按照权值从大到小删除，当我们删掉一条边的 \((u,v)\) 的时候，可以发现一定存在一种方案使得初始钱数为 \(r\) 就能无限走下去，那么此时对 \(u\) 的答案的贡献为 \(ans_{u}=min(ans_{u},r)\)。
在删掉这条边之后，可能又会有一些点无法到达强连通分量，继续做拓扑，把那些边删掉，并在过程中维护一下答案就可以了， \(ans_{u}=\min(ans_{u},\max(ans_{v}-p,r))\)
Code
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cassert>
using namespace std;
#define ll long long
#define ri int
#define pii pair<int,int>
const ll mod=998244353;
ll add(ll x,ll y){return (x+=y)<mod?x:x-mod;}
ll dec(ll x,ll y){return (x-=y)<0?x+mod:x;}
ll ksm(ll d,ll t,ll res=1){for(;t;t>>=1,d=d*d%mod) if(t&1) res=res*d%mod;return res;}
const int MAXN=2e5+7;
int n,m;
struct edge{
int u,v,r,w;
bool operator<(const edge p)const{
return r<p.r;
}
}e[MAXN];
const int inf=2e9;
int f[MAXN],cnt;
bool cmp(int x,int y){return e[x].w<e[y].w;}
vector<int> g[MAXN],rg[MAXN];
int ans[MAXN],mark[MAXN],deg[MAXN],del[MAXN];
int main(){
// freopen("rand.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
for(ri i=1;i<=n;++i) ans[i]=inf;
for(ri i=1;i<=m;++i){
int u,v,r,w;scanf("%d%d%d%d",&u,&v,&r,&w);
e[i]=(edge){u,v,r,w};
}
sort(e+1,e+m+1);
for(ri i=1;i<=m;++i) g[e[i].u].push_back(i),rg[e[i].v].push_back(i);
for(ri i=1;i<=m;++i) deg[e[i].u]++;
queue<int> q;
for(ri i=1;i<=n;++i) if(!deg[i]) q.push(i);
while(!q.empty()){
int u=q.front();q.pop();
mark[u]=1;
for(auto x:rg[u]){
del[x]=1;
int v=e[x].u;
if(!--deg[v]) q.push(v);
}
}
for(ri i=m;i;--i){
if(del[i]) continue;
del[i]=1;
ans[e[i].u]=min(ans[e[i].u],e[i].r);
if(!--deg[e[i].u]) q.push(e[i].u);
while(!q.empty()){
int u=q.front();q.pop();
assert(!mark[u]);
mark[u]=1;
for(auto x:rg[u]) {
if(del[x]) continue;
del[x]=1;
ans[e[x].u]=min(ans[e[x].u],max(ans[u]-e[x].w,e[x].r));
if(!--deg[e[x].u]) q.push(e[x].u);
}
}
}
for(ri i=1;i<=n;++i) printf("%d ",ans[i]==inf?-1:ans[i]);
}