rt，用的是Bellman-Ford+Dijkstra的Johnson

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define int long long
const int INF=1e9;
inline void write(int x) 
{
    if(x<0) 
    { 
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar((x%10)^48);
}
inline int read()
{
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*w;
}
struct edge
{
    int u,v,w;
};
int n,m,cnt,h[3005],to[6005],val[6005],nxt[6005];
vector<edge> g;
inline void add(int a,int b,int c)
{
    to[++cnt]=b;
    val[cnt]=c;
    nxt[cnt]=h[a];
    h[a]=cnt;
    return;
}
int tmp[3005],dis[3005],ans;
inline bool bellmanford(int s)
{
    fill(tmp+1,tmp+n+1,INF);
    tmp[s]=0;
    bool flag=0;
    for(int i=1;i<=n;i++)
    {
        flag=0;
        for(auto j:g)
        {
            int u=j.u,v=j.v,w=j.w;
            if(tmp[u]==INF) continue;
            if(tmp[v]>tmp[u]+w)
            {
                tmp[v]=tmp[u]+w;
                flag=1;
            }
        }
        if(!flag) break;
    }
    return flag;
}
inline void dijkstra(int s)
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    fill(dis+1,dis+n+1,INF);
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        for(int i=h[u];i;i=nxt[i])
        {
            int v=to[i];
            if(dis[v]>dis[u]+val[i])
            {
                dis[v]=dis[u]+val[i];
                q.push(make_pair(dis[v],v));
            }
        }
    }
    return;
}
inline bool johnson()
{
    for(int i=1;i<=n;i++) g.push_back(edge{0,i,0});
    if(bellmanford(0)) return 1;
    for(int i=0;i<cnt;i++)
    {
        int u=g[i].u,v=g[i].v;
        val[i+1]+=tmp[u]-tmp[v];
    }
    for(int i=1;i<=n;i++)
    {
        dijkstra(i);
        int ans=0;
        for(int j=1;j<=n;j++)
        {
            if (dis[j] == INF) ans += j * INF;
            else ans += j * (dis[j] + h[j] - h[i]);
        }
        write(ans);
        putchar('\n');
    }
    return 0;
}
signed main()
{
    n=read();
    m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        add(u,v,w);
        g.push_back(edge{u,v,w});
    }
    if(johnson()) write(-1);
    return 0;
}

样例：

5 7
1 2 4
1 4 10
2 3 7
4 5 3
4 2 -2
3 4 -3
5 3 4

样例输出：

128
1000000072
999999978
1000000026
1000000014

我的输出：

201
1000000061
999999995
1000000015
1000000017

目前推测应该是求和的地方有问题