8pts 万花从中一株草

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=10005;
struct Edge{
	int v,w,nxt;
}edge[N];
struct node{
	int u,d;
	bool operator<(const node& a)const{
		return d>a.d;
	}
};
int head[N],sp_dis[N],ans[N],dis[N];
bool vis[N];
int n,m,f,t,k,cnt;
void add(int u,int v,int w){
	edge[++cnt]=Edge{v,w,head[u]};
	head[u]=cnt;
	return ;
}
void spfa(int st){
	queue<int>q;
	fill(sp_dis,sp_dis+1+N,1e9);
	sp_dis[st]=0;
	vis[st]=1;
	q.push(st);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].nxt){
			if(sp_dis[edge[i].v]>sp_dis[u]+edge[i].w){
				sp_dis[edge[i].v]=sp_dis[u]+edge[i].w;
				if(!vis[edge[i].v]){
					vis[edge[i].v]=1;
					q.push(edge[i].v);
					ans[edge[i].v]++;
					if(ans[edge[i].v]==n+1){
						cout<<-1;
						exit(0);
					}
				}
			}
		}
	}
	return ;
}
void dijkstra(int st){
	priority_queue<node>q;
	fill(dis,dis+1+N,1e9);
	memset(vis,0,sizeof(vis));
	dis[st]=0;
	q.push(node{st,0});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u]){
			continue;
		}
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].nxt)
			if(dis[edge[i].v]>dis[u]+edge[i].w){
				dis[edge[i].v]=dis[u]+edge[i].w;
				if(!vis[edge[i].v]){
					vis[edge[i].v]=1;
					q.push(node{edge[i].v,dis[edge[i].v]});
				}
			}
	}
	return ;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>f>>t>>k;
		add(f,t,k);
	}
	for(int i=1;i<=n;i++) add(0,i,0);
	spfa(0);
	for(int u=1;u<=n;u++)
		for(int i=head[u];i;i=edge[i].nxt){
			edge[i].w+=sp_dis[u]-sp_dis[edge[i].v];
		}
	for(int i=1;i<=n;i++){
		dijkstra(i);
		int sum=0;
		for(int j=1;j<=n;j++)
			if(dis[j]==1e9) sum+=j*1e9;
			else sum+=j*(dis[j]+sp_dis[j]-sp_dis[i]);
		cout<<sum<<endl;
	}
	return 0;
}