题号是P5905 Johnson全源最短路
//C++98 https://www.luogu.com.cn P5905
//Include
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
//Const
const int Maxn=4e3;
const int Maxm=7e5;
const int Inf=0x7f7f7f7f;
//Struct
struct _Graph_Line
{
int x,y,next;
int s;
};
struct _Graph_Heap_Cmp
{
int *d;_Graph_Heap_Cmp(int *d){this->d=d;}
bool operator()(int a,int b){return d[a]>d[b];}
};
struct _Graph
{
int d[Maxn],c[Maxn],f[Maxn],h[Maxn];bool v[Maxn];int n;
priority_queue<int,vector<int>,_Graph_Heap_Cmp>H;queue<int>Q;
_Graph_Line line[Maxm];int len,last[Maxn];
_Graph():H(_Graph_Heap_Cmp(d)){Clean();}
inline void Clean(){len=0;memset(last,-1,sizeof(last));}
inline void Insert(int x,int y,int s)
{
line[len].x=x;line[len].y=y;line[len].s=s;
line[len].next=last[x];last[x]=len++;
}
inline void Init_Queue(int st)
{
memset(d, 0x7f,sizeof(d));d[st]=0;
memset(c, 0 ,sizeof(c));c[st]=1;
memset(f, -1 ,sizeof(f));f[st]=st;
while(!Q.empty())Q.pop();Q.push(st);
}
inline void Init_Heap(int st)
{
memset(d, 0x7f,sizeof(d));d[st]=0;
memset(f, -1 ,sizeof(f));f[st]=st;
while(!H.empty())H.pop();H.push(st);
}
inline bool Bellman_Ford_Queue(int st)
{
memset(v,false,sizeof(v));v[st]=true;
Init_Queue(st);
while(!Q.empty())
{
int x=Q.front();Q.pop();v[x]=false;
for(int k=last[x];k!=-1;k=line[k].next)
{
int y=line[k].y;
if(d[y]>d[x]+line[k].s)
{
d[y]=d[x]+line[k].s;f[y]=x;c[y]=c[x]+1;
if(c[y]>n)return true;
if(v[y]==false)
{
v[y]=true;
Q.push(y);
}
}
}
}
return false;
}
inline void Bellman_Ford_Heap(int st)
{
memset(v,false,sizeof(v));v[st]=true;
Init_Heap(st);
while(!H.empty())
{
int x=H.top();H.pop();v[x]=false;
for(int k=last[x];k!=-1;k=line[k].next)
{
int y=line[k].y;
if(d[y]>d[x]+line[k].s)
{
d[y]=d[x]+line[k].s;f[y]=x;
if(v[y]==false)
{
v[y]=true;
H.push(y);
}
}
}
}
}
inline void Dijkstra_Heap(int st)
{
memset(v,false,sizeof(v));
Init_Heap(st);
while(!H.empty())
{
int x=H.top();H.pop();
if(v[x]==true)continue;
else
{
v[x]=true;printf("%d ",x);
for(int k=last[x];k!=-1;k=line[k].next)
{
int y=line[k].y;
if(d[y]>d[x]+line[k].s)
{
d[y]=d[x]+line[k].s;f[y]=x;
if(v[y]==false)H.push(y);
}
}
}
}
}
inline bool Johnson()
{
int st=0;
for(int i=1;i<=n;i++)Insert(st,i,0);
if(Bellman_Ford_Queue(st)==true)return true;
else
{
for(int k=0;k<=len;k++)
{
int x=line[k].x;
int y=line[k].y;
h[x]=d[x];h[y]=d[y];
line[k].s+=h[x]-h[y];
}
return false;
}
}
};
_Graph G;int m;
int main()
{
freopen("Bug.txt","w",stdout);
scanf("%d%d",&G.n,&m);
for(int i=1;i<=m;i++)
{
int x,y,s;
scanf("%d%d%d",&x,&y,&s);
G.Insert(x,y,s);
}
if(G.Johnson()){printf("-1");return 0;}
for(int i=1;i<=G.n;i++)
{
long long ans;ans=0;
G.Dijkstra_Heap(i);
for(int j=1;j<=G.n;j++)
{
long long s1=(G.d[j]==Inf?1e9:G.d[j]);
long long s2=(G.h[j]-G.h[i]);
if(s1==1e9)ans+=j*1e9;
else ans+=j*(s1+s2);
}
printf("%lld\n",ans);
}
return 0;
}