rt

前缀为sf的代表spfa使用的

前缀为dj的代表dij使用的（除dis数组外）

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define up(i,j,k,l) for(int i=j;i<=k;i+=l)
#define down(i,j,k,l) for(int i=j;i>=k;i-=l)
using namespace std;
const int N=3e3+10;
int n,m;
int u,v,w;
vector< pair<int,int> > vc[N];
ll dis[N];
int sfd[N],sfct[N];
bool sff[N],djf[N];
queue<int> sfq;
priority_queue< pair<ll,int>,vector< pair<ll,int> >,greater< pair<ll,int> > > djq;
ll ans;
void dij(int e)
{
	while(!djq.empty()){
		djq.pop();
	}
	djq.push({0,e});
	up(i,1,n,1){
		dis[i]=1e15;
	}
	dis[e]=0;
	while(!djq.empty()){
		u=djq.top().second;
		djq.pop();
		if(djf[u]==true){
			continue;
		}
		djf[u]=true;
		for(auto fw:vc[u]){
			if(dis[fw.first]>dis[u]+fw.second){
				dis[fw.first]=dis[u]+fw.second;
				if(djf[fw.first]==false){
					djq.push({dis[fw.first],fw.first});
				}
			}
		}
	}
	return;
}
bool spfa()
{
	sfq.push(0);
	memset(sfd,0x3f3f3f,sizeof sfd);
	sfd[0]=0;
	sff[0]=true;
	while(!sfq.empty()){
		u=sfq.front();
		sfq.pop();
		sff[u]=false;
		for(auto fw:vc[u]){
			if(sfd[fw.first]>sfd[u]+fw.second){
				sfd[fw.first]=sfd[u]+fw.second;
				if(sff[fw.first]==false){
					sff[fw.first]=true;
					sfq.push(fw.first);
					sfct[fw.first]++;
					if(sfct[fw.first]>=n+1){
						return false;
					}
				}
			}
		}
	}
	return true;
}
void solve()
{
	cin>>n>>m;
	up(i,1,m,1){
		cin>>u>>v>>w;
		vc[u].push_back({v,w});
	}
	up(i,1,n,1){
		vc[0].push_back({i,0}); 
	}
	if(spfa()==false){
		puts("-1");
		return;
	}
	up(i,1,n,1){
		up(j,0,(int)vc[i].size()-1,1){
			vc[i][j].second=sfd[i]-sfd[vc[i][j].first];
		}
	}
	up(i,1,n,1){
		dij(i);
		ans=0;
		up(j,1,n,1){
			if(dis[j]==1e15){
				ans+=j*1e9;
			}
			else{
				ans+=j*(dis[j]+sfd[j]-sfd[i]);
			}
		}
		cout<<ans<<endl;
	}
	return;
}
int main()
{
    //ios::sync_with_stdio(false);
	//cin.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int _=1;
	//cin>>_;
	up(i,1,_,1){
		solve();
	}
	return 0;
}