用了最普通的方法，先跑一遍SPFA判负环，然后跑n遍Dijkstra求最短路，只有40分不知道怎么改了，求大佬们看一看！

#include<queue>
#include<cstdio>
#define oo 1e9
using namespace std;
int n,m,a,b,c,tmp,head[1000001];
long long dis[1000001],das[1000001],vis[1000001],vas[1000001],t[1000001];
struct node{
	int to,w,next;
}e[90000001];
void add(int x,int y,int z){
	e[tmp].to=y;
	e[tmp].w=z;
	e[tmp].next=head[x];
	head[x]=tmp++; 
}
bool spfa(int x){
	queue<int>q;
	dis[x]=0;
	vis[x]=1;
	q.push(x);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=-1;i=e[i].next){
			if(dis[e[i].to]>dis[u]+e[i].w){
				dis[e[i].to]=dis[u]+e[i].w;
				if(!vis[e[i].to]){
					++t[e[i].to];
					if(t[e[i].to]>=n) return false;
					vis[e[i].to]=1;
					q.push(e[i].to);
				}
			}
		}
	}
	return true;
}
void dijkstra(int x){
	priority_queue<pair<long long,int> >q;
	for(int i=1;i<=n;++i) das[i]=oo,vas[i]=0;
	das[x]=0;
	q.push(make_pair(0,x));
	while(!q.empty()){
		int k=q.top().second;
		q.pop();
		for(int i=head[k];i!=-1;i=e[i].next){
			if(das[e[i].to]>das[k]+e[i].w){
				das[e[i].to]=das[k]+e[i].w;
				if(!vas[e[i].to]){
					vas[e[i].to]=1;
					q.push(make_pair(-das[e[i].to],e[i].to));
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;++i) head[i]=-1;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	for(int i=1;i<=n;++i) dis[i]=oo,add(0,i,0);
	if(!spfa(0)){
		printf("-1");
		return 0;
	}
	for(int i=1;i<=n;++i){
		for(int j=head[i];j!=-1;j=e[j].next){
			e[j].w+=dis[i]-dis[e[j].to];
		}
	}
	for(int i=1;i<=n;++i){
		dijkstra(i);
		long long ans=0;
		for(int j=1;j<=n;++j){
			if(das[j]==oo) ans+=1e9*j;
			else ans+=(das[j]-dis[i]+dis[j])*j;
		}
		printf("%lld\n",ans);
	}
	return 0;
}