rt

样例1都还没过

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
	int distance,subscript;
	friend bool operator < (node a,node b){
		return a.distance > b.distance;
	}
};
struct EDGE{
	int v,w,nxt;
}edge[6010];
priority_queue<node>pq;
queue<int>q;
int n,m,edge_cnt;
int head[6010];
int dis[3010],stic[3010],times[3010];
bool book[3010];
void add(int u,int v,int w){
	edge[++edge_cnt].v=v;
	edge[edge_cnt].w=w;
	edge[edge_cnt].nxt=head[u];
	head[u]=edge_cnt;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int i=1;i<=n;i++) add(0,i,0);

	memset(stic,0x7f,sizeof stic);
	stic[0]=0;
	book[0]=1;
	q.push(0);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		book[u]=0;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].v;
			int w=edge[i].w;
			if(stic[v]>stic[u]+w){
				stic[v]=stic[u]+w;
				if(!book[v]){
					q.push(v);
					book[v]=1;
					times[v]++;
					if(times[v]==n+1){
						cout<<-1;
						return 0;
					}
				}
			}
		}
	}
	for(int u=1;u<=n;u++){
		for(int i=head[u];i;i=edge[i].nxt){
			edge[i].w+=(stic[u]-stic[edge[i].v]);
		}
	}
	for(int j=1;j<=n;j++){
		for(int i=1;i<=n;i++){
			dis[i]=1e9;
			book[i]=0;
		}
		while(!pq.empty()) pq.pop();
		book[j]=1;
		dis[j]=0;
		pq.push((node){0,j});
		while(!pq.empty()){
			int u=pq.top().subscript;
			pq.pop();
			if(book[u]) continue;
			book[u]=1;
			for(int i=head[u];i;i=edge[i].nxt){
				int v=edge[i].v;
				int w=edge[i].w;
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					pq.push((node){v,dis[v]});
				}
			}
		}
		ll sum=0;
		for(int i=1;i<=n;i++) sum+=i*dis[i];
		cout<<sum<<endl;
	}

	return 0;
}