第 $5$ 个点 TLE。 因该输出 $-1$，而我没有。

代码：

#include <bits/stdc++.h>
#define int long long
#define ld long double
#define ull unsigned long long

#define mk make_pair
#define vi vector<int>
#define PI pair<int,int>
#define dg priority_queue<int,vector<int> >
#define xg priority_queue<int,vector<int>,greater<int> >

#define co const
#define ff  first
#define ss  second
#define il inline
#define re register
#define ls(p) p<<1
#define rs(p) p<<1|1
#define pb push_back
#define ch(i) (i-'a')
#define bit(x) (x&-x)
#define md(x,y) (x+y)>>1
#define all(x) x.begin(),x.end()
#define swap(a,b) a^=b,b^=a,a^=b
#define sort_(a,n) sort(a+1,a+n+1)
#define m(a,x) memset(a,x,sizeof a)
#define abs(x) ((x^(x>>63))-(x>>63))
#define keep(n) fixed<<setprecision(n)
#define FOR2(i,a,n) for(int (i)=(n); (i)>=(a); (i)--)
#define FOR(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define cios cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define fre(k) freopen(k".in","r",stdin),freopen(k".out","w",stdout)

#define ps puts("")
#define kg cout<<" "
#define db(x) cout<<#x<<'='<<x<<"\n"
#define pes {puts("Yes"); return 0;}
#define pno {puts("No"); return 0;}
#define pfu {puts("-1"); return 0;}
#define dbgg cout<<"-------------------------\n"
#define debug(x,n) for(int i=1; i<=(n); i++) cout<<x[i]<<" "
using namespace std;
const int N=5005,M=10005;
const int P=998244353;
const int INF=1e9;
const int eps=1e-6;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x/gcd(x, y)*y;}
int ksm(int a,int b){int ans=1;for(;b;a=(a*a)%P,b>>=1)if(b&1)ans=(ans*a)%P;return ans;}
int read(){
    int xo=0,fo=1;char cp;
    while((cp=getchar())<'0'||cp>'9')if(cp=='-')fo=-1;
    while(cp>='0'&&cp<='9')xo=(xo<<3)+(xo<<1)+(cp^48),cp=getchar();
    return xo*fo;
}
void w(int x) {
  if(x<0)x=-x,putchar('-');
  if(x>9)w(x/10);
  putchar(x%10+'0');
}
void read2(int &a,int &b){a=read(),b=read();}
void read3(int &a,int &b,int &c){a=read(),b=read(),c=read();}
void read4(int &a,int &b,int &c,int &d){a=read(),b=read(),c=read(),d=read();}
void readk(int a[],int n){for(int i=1; i<=n; i++) a[i]=read();}
int n,m,h[N],dis[N];
int tot,hd[N],nxt[M],to[M],dt[M];
bool vis[N];
void add(int x,int y,int w){
	tot++;
	nxt[tot]=hd[x];
	hd[x]=tot;
	to[tot]=y;
	dt[tot]=w;
}
bool spfa(int s){
	queue<int> q;
	for(int i=1; i<=n; i++) h[i]=INF,vis[i]=0;
	h[s]=0;vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=0;
		for(int i=hd[u]; i; i=nxt[i])
			if(h[to[i]]>h[u]+dt[i]){
				h[to[i]]=h[u]+dt[i];
				if(!vis[to[i]]){
					if(++vis[to[i]]>=n+1) return 0;
					vis[to[i]]=1;
					q.push(to[i]);
				}
			}
	} 
	return 1;
}
void dij(int s){
	priority_queue<PI,vector<PI>,greater<PI> >q;
	for(int i=1; i<=n; i++) dis[i]=INF,vis[i]=0;
	q.push(mk(0,s));
	dis[s]=0;
	while(!q.empty()){
		int u=q.top().ss;
		q.pop();
		if(!vis[u]){
			vis[u]=1;
			for(int i=hd[u]; i; i=nxt[i])
				if(dis[to[i]]>dis[u]+dt[i]){
					dis[to[i]]=dis[u]+dt[i];
					if(!vis[to[i]]) q.push(mk(dis[to[i]],to[i]));
				}
		}
	}
}
signed main(){
	read2(n,m);
	for(int i=1; i<=m; i++){
		int u,v,w;
		read3(u,v,w);
		add(u,v,w);
	}
	for(int i=1; i<=n; i++) add(0,i,0);
	if(!spfa(0)) pfu
	for(int i=1; i<=n; i++)
		for(int j=hd[i]; j; j=nxt[j])
			dt[j]+=h[i]-h[to[j]];
	for(int i=1; i<=n; i++){
		dij(i);
		int ans=0;
		for(int j=1; j<=n; j++){
			if(dis[j]==INF) ans+=1ll*j*INF;
			else ans+=1ll*j*(dis[j]+(h[j]-h[i]));
		}
		w(ans),ps;
	}
	return 0;
}