rt

code:

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N=3e3+5,INF=0x3f3f3f3f3f3f3f3f;
struct Edge
{
	int v,w;
};
bool vis[N];
int n,m,u,v,w,dis[N][N];
vector<Edge>edge[N];
void build(int u,int v,int w)
{
	edge[u].push_back((Edge){v,w});
}
bool bellman_ford(int start)
{
	memset(dis[start],127,sizeof dis[start]);
	dis[start][start]=0;
	bool flag;
	for(int i=1;i<=n;i++)
	{
		flag=false;
		for(int u=1;u<=n;u++)
		for(auto tmp:edge[u])
		{
			int v=tmp.v,w=tmp.w;
			if(dis[start][v]>dis[start][u]+w)
				dis[start][v]=dis[start][u]+w,flag=true;
		}
		if(!flag)break;
	}
	return flag;
}
void dijkstra(int start)
{
	memset(vis,false,sizeof vis);
	memset(dis[start],127,sizeof dis[start]);
	priority_queue<PII,vector<PII>,greater<PII> >que;
	dis[start][start]=0,que.push(make_pair(0,start));
	while(!que.empty())
	{
		int u=que.top().second;
		vis[u]=true,que.pop();
		for(auto tmp:edge[u])
		{
			int v=tmp.v,w=tmp.w;
			if(!vis[v]&&dis[start][v]>dis[start][u]+w)
			{
				dis[start][v]=dis[start][u]+w;
				que.push(make_pair(dis[start][v],v));
			}
		}
	}
}
void johnson()
{
	for(int i=1;i<=n;i++)
		build(0,i,0);
	bool flag=bellman_ford(0);
	if(flag)
	{
		cout<<-1;
		return;
	}
	for(int u=1;u<=n;u++)
	for(int i=0;i<edge[u].size();i++)
		edge[u][i].w+=dis[0][u]-dis[0][edge[u][i].v];
	for(int u=1;u<=n;u++)
		dijkstra(u);
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		for(int j=1;j<=n;j++)
		{
			dis[i][j]-=dis[0][i]-dis[0][j];
			if(i==j)dis[i][j]=0;
			if(dis[i][j]>=INF)dis[i][j]=1e9;
			ans+=j*dis[i][j];
		}
		cout<<ans<<'\n';
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>u>>v>>w,build(u,v,w);
	johnson();
	return 0;
}