代码如下：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 3001

struct Edge{
	int v, w;
};

struct Node{
	int u, dis;
	bool operator>(const Node a)const{
		return dis > a.dis;
	}
};

int n, m, u, v, w;
int cnt[MAXN];
long long ans;
long long h[MAXN], dis[MAXN];
bitset<MAXN> vis;
vector<Edge> e[MAXN];
queue<int> que;
priority_queue<Node, deque<Node>, greater<Node>> pq;

bool spfa(int s){
	h[s] = 0;
	vis[s] = true;
	que.push(s);
	
	while (!que.empty()){
		u = que.front();
		que.pop();
		vis[u] = false;
		for (auto i: e[u]){
			v = i.v;
			w = i.w;
			if (h[v] > h[u] + w){
				h[v] = h[u] + w;
				cnt[v] = cnt[u] + 1;
				if (cnt[v] >= n) return false;
				if (!vis[v]){
					que.push(v);
					vis[v] = true;
				}
			}
		}
	}
	
	return true;
}

void dijkstra(int s){
	dis[s] = 0;
	pq.push({s, 0});
	while (!pq.empty()){
		u = pq.top().u;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto i: e[u]){
			v = i.v;
			w = i.w;
			if (dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				pq.push({v, dis[v]});
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	
	for (int i=1; i<=m; i++){
		cin >> u >> v >> w;
		e[u].push_back({v, w}); 
	}
	for (int i=1; i<=n; i++) e[0].push_back({i, 0});
	
	memset(h, 0x3f, sizeof(h));
	if (!spfa(0)){
		cout << -1;
		return 0;
	}
	
	for (int i=1; i<=n; i++){
		for (auto &j: e[i]) j.w += h[i] - h[j.v];
	}
	
	for (int i=1; i<=n; i++){
		for (int i=1; i<=n; i++) dis[i] = 1e9;
		vis.reset();
		dijkstra(i);
		ans = 0;
		for (int j=1; j<=n; j++) ans += j * (dis[j] == 1e9 ? dis[j] : dis[j]+h[j]-h[i]);
		cout << ans << '\n';
	}
	
	return 0;
}

评测记录