RT，思路是一遍 SPFA + $n$ 遍 Dijkstra。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
const int M=6005;
const int INF=1e9;
typedef pair<int,int> pii;
typedef long long ll;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') f=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
void put(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) put(x/10);
	putchar((x%10)^48);
}
int n,m;
int head[N],nxt[M],from[M],ver[M],cst[M],tot;
int h[N],dis[N],l[N],vis[N];
queue<int> Q;
priority_queue<pii,vector<pii>,greater<pii> > QQ;
void add(int w,int v,int u){
	ver[++tot]=v;
	from[tot]=u;
	cst[tot]=w;
	nxt[tot]=head[u];
	head[u]=tot;
}
void SPFA(){
	memset(h,63,sizeof(h));
	h[0]=0,vis[0]=1,Q.push(0);
	while(!Q.empty()){
		int u=Q.front();vis[u]=0;Q.pop();
		for(int i=head[u];~i;i=nxt[i]){
			int v=ver[i],w=cst[i];
			if(h[u]+w<h[v]){
				h[v]=h[u]+w;
				l[v]=l[u]+1;
				if(l[v]>n) exit(puts("-1")&0);
				if(!vis[v]) vis[v]=1,Q.push(v);
			}
		}
	}
	for(int i=1;i<=tot;i++) cst[i]+=h[from[i]]-h[ver[i]];
}
void Dijkstra(int s){
	for(int i=1;i<=n;i++) dis[i]=INF; 
	QQ.push(make_pair(dis[s]=0,s));
	while(!QQ.empty()){
		int u=QQ.top().second,d=QQ.top().first;QQ.pop();
		if(dis[u]!=d) continue;
		for(int i=head[u];~i;i=nxt[i]){
			int v=ver[i],w=cst[i];
			if(dis[u]+w<dis[v]) QQ.push(make_pair(dis[v]=dis[u]+w,v));
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++) ans+=(ll)i*(dis[i]+(dis[i]==INF?0:h[i]-h[s]));
	put(ans),putchar(10);
}
int main(){
	memset(head,-1,sizeof(head));
	n=read(),m=read();
	while(m--) add(read(),read(),read());
	for(int i=1;i<=n;i++) add(0,i,0);
	SPFA();
	for(int i=1;i<=n;i++) Dijkstra(i);
	return 0;
}

惨案

莫名 TLE，甚至只运行判负环的 SPFA() 函数都 TLE 了两点。