RT，28分求助

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=10005,inf=1e9;
ll head[maxn],ver[maxn],nxt[maxn],wei[maxn];
ll d[maxn];
ll n,m,tot;
ll h[maxn];
bool v[maxn];
ll t[maxn];
void add(int x,int y,int z){
	nxt[++tot]=head[x];
	head[x]=tot;
	ver[tot]=y;
	wei[tot]=z;
}
bool spfa(int x){
	queue<int>q;
	memset(h,63,sizeof(h));
	memset(v,0,sizeof(v));
	h[x]=0;
	v[x]=1;
	q.push(x);
	t[x]++;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		v[x]=0;
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i],z=wei[i];
			if(h[y]>h[x]+h[z]){
				h[y]=h[x]+h[z];
				if(!v[y]){
					v[y]=1;
					q.push(y);
					t[y]++;
					if(t[y]==n)return 0;
				}
			}
		}
	}
	return 1;
}
void dijkstra(int x){
	priority_queue<pair<int,int> >q;
	for(int i=1;i<=n;i++){
		d[i]=inf;
	}
	memset(v,0,sizeof(v));
	d[x]=0;
	q.push(make_pair(0,x));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		v[x]=1;
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i],z=wei[i];
			if(v[y])continue;
			if(d[y]>d[x]+z){
				d[y]=d[x]+z;
				q.push(make_pair(-d[y],y));
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	for(int i=1;i<=n;i++){
		add(0,i,0);
	}
	if(!spfa(0)){
		cout<<"-1\n";
		return 0;
	}
	for(int x=1;x<=n;x++){
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			wei[i]+=h[x]-h[y];
		}
	}
	for(int i=1;i<=n;i++){
		dijkstra(i);
		ll ans=0;
		for(int j=1;j<=n;j++){
			if(d[j]==inf)ans+=j*inf;
			else ans+=j*(d[j]-h[i]+h[j]);
		}
		cout<<ans<<"\n";
	}
}