普通的 Johnson ，TLE 了两个点，哪位大佬帮忙调一下。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e9;
const int maxn = 1e4+100;
int n,m;
int use[maxn],cnt[maxn];
int dis[3010][3010],h[maxn],head[maxn];
struct star{
    int v;
    int nxt;
    int w;
}edge[maxn];
int tot;
void add(int u,int v,int w){
    edge[++tot].v=v;
    edge[tot].nxt=head[u];
    edge[tot].w=w;
    head[u]=tot;
}
int SPFA(int s){
    queue<int> q;
    for(int i=0;i<=n;i++){
        use[i]=cnt[i]=0;
        h[i]=inf;
    }
    q.push(s);
    use[s]=1;
    h[s]=0;
    while(!q.empty()){
        int f=q.front();
        q.pop();
        use[f]=0;
        for(int i = head[f]; i != -1; i = edge[i].nxt)
        {
            if(h[f]+edge[i].w<h[edge[i].v]){
                h[edge[i].v]=h[f]+edge[i].w;
                // cout<<edge[f][i].first<<' '<<dis[edge[f][i].first]<<'\n';
                
                if(!use[edge[i].v]){
                cnt[edge[i].v]++;
                    use[edge[i].v]=1;
                    q.push(edge[i].v);
                    if(cnt[edge[i].v]>n + 1){
                        return -1;
                    }
                }
            }
        }
    }
    return 1;
}
void inti(){
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=edge[j].nxt){
            
            edge[j].w+=(h[i]-h[edge[j].v]);
        }
    }
}
void dij(int s){
    priority_queue< pair<int,int> ,vector< pair<int,int> > ,greater< pair<int,int> > > D;
    for(int i=1;i<=n;i++) use[i]=0;
    for(int i=1;i<=n;i++) dis[s][i]=inf;
    use[s]=1;
    dis[s][s]=0;
    D.push(make_pair(0,s));
    while(D.size()>0){
        pair<int,int> f=D.top();
        use[f.second]=1;
        D.pop();
        for(int i=head[f.second];i != -1;i=edge[i].nxt){
            int p=edge[i].v;
            if(use[p]==0&&dis[s][p]>dis[s][f.second]+edge[i].w){
                dis[s][p]=dis[s][f.second]+edge[i].w;
                D.push(make_pair(dis[s][p],p));
            }
        }
    }
}
signed main(){
    cin>>n>>m;
    for(int i = 0;i <= 10000;i++)
        head[i] = -1;
    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);
    }
    if(SPFA(0)==-1){
        cout<<"-1\n";
        return 0;
    }
    inti();
    for(int i=1;i<=n;i++){
        dij(i);
    }
    for(int i=1;i<=n;i++){
        int res=0;
        for(int j=1;j<=n;j++){
            //cout<<i<<' '<<j<<' '<<dis[i][j]+h[j]-h[i]<<'\n';
            if(dis[i][j]!=1000000000)
                res+=j*(dis[i][j]+h[j]-h[i]);
            else
                res+=j*1000000000;
        }
        cout<<res<<'\n';
    }
}
//1 2 9
//1 4 13
//2 3 2
//4 5 0
//4 2 0
//3 4 0
//5 3 4
//