68,不知道为什么卡死了 MLE3 TLE1

#include<bits/stdc++.h>
#define FAST() ios::sync_with_stdio(0),cin.tie(nullptr)
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define _rep(a,b,c) for(int a=b;a>=c;a--)
#define __rep(a,b) for(auto a:b)
#define yEs cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define pii pair<int,int>
#define psi pair<string,int>
#define Ss stringstream
#define pci pair<char,int>
#define mii map<int,int>
#define pq prioriry_queue
#define msi map<string,int>
#define mci map<char,int>
#define debug(x) cout<<#x<<":"<<(x)<<" "
#define mem(x,y) memset(x,y,sizeof x)
#define fir first
#define se second
#define endl '\n'
#define int long long
#define INT_MAX LONG_LONG_MAX
using namespace std;
static const int N=6e2+114;
const int inf = 1e9;

inline int read() {
	int w=1,c,ret;
	while((c=getchar())>'9'||c< '0')w=(c=='-'?-1:1);
	ret=c-'0';
	while((c=getchar())>='0'&&c<='9')ret=ret*10+c-'0';
	return ret*w;
}
const int mod = 1000000007;
const int lenm=3;


int n,m;
const int graphmx=6e3+114;

const int dense=2;
struct John {
	struct edg {
		int next,to;
		int w;
	} edge[graphmx*dense];
	int head[graphmx];
	int cnt=0;
	int h[graphmx];
	bool f[graphmx];
	int vis[graphmx];
	void add_edge(int u, int v, int w) {
		edge[++cnt].to=v;
		edge[cnt].next=head[u],edge[cnt].w=w;
		head[u]=cnt;
	}
	vector<int> dij(int s) {
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int, int>>>pq;
		vector<int>dis(graphmx,inf);
		dis[s]=0;
		pq.push({0, s});
		while (!pq.empty()) {
			auto[d,u]=pq.top();
			pq.pop();
			if (d>dis[u])continue;
			for (int i=head[u]; i; i=edge[i].next) {
				int v=edge[i].to;
				if (dis[v]>dis[u]+edge[i].w) {
					dis[v]=dis[u]+edge[i].w;
					pq.emplace(dis[v],v);
				}
			}
		}

		return dis;
	}
	bool spfa(int s) {
		queue<int>q;
		for(int i=1; i<=n; ++i) h[i]=inf,f[i]=false;
		h[s]=0;
		f[s]=true;
		q.push(s);
		while(!q.empty()) {
			int xx=q.front();
			q.pop();
			f[xx]=false;
			for(int i=head[xx]; i; i=edge[i].next)
				if(h[edge[i].to]>h[xx]+edge[i].w) {
					h[edge[i].to]=h[xx]+edge[i].w;
					if(!f[edge[i].to]) {
						if(++vis[edge[i].to]>=n+1)return false;
						f[edge[i].to]=true,q.push(edge[i].to);
					}
				}
		}
		return true;
	}

	pair<bool,vector<vector<int>>> johnson() {
		vector<vector<int>>diss;
		if(!spfa(0)) {
			return {1,diss};
		}
		rep(u,1,n)
		for(int i=head[i]; i; i=edge[i].next)
			edge[i].w+=h[u]-h[edge[i].to];
		rep(i,0,n) {
			vector<int> ANs=dij(i);
			diss.emplace_back(ANs);
		}
		return {0,diss};
	}

} John;
struct graph {
	struct edg {
		int next,to;
		int w;
	} edge[graphmx*dense];
	bool Primvis[graphmx];
	int head[graphmx];
	int cnt=0;
	graph() {
		memset(Primvis,0,sizeof Primvis);
		memset(head,0,sizeof head);
		Primvis[1]=1;

	}
	void add_edge(int u,int v,int w) {
		edge[++cnt].to=v;
		edge[cnt].next=head[u],edge[cnt].w=w;
		head[u]=cnt;
	}
	vector<int>dij(int s) {
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int, int>>>pq;
		vector<int>dis(graphmx,inf);
		dis[s]=0;
		pq.push({0, s});
		while (!pq.empty()) {
			auto[d,u]=pq.top();
			pq.pop();
			if (d>dis[u])continue;
			for (int i=head[u]; i; i=edge[i].next) {
				int v=edge[i].to;
				if (dis[v]>dis[u]+edge[i].w) {
					dis[v]=dis[u]+edge[i].w;
					pq.emplace(dis[v],v);
				}
			}
		}
		return dis;
	}
	pair<vector<int>,bool>spfa(int s) {
		vector<int>dis(graphmx,inf);
		vector<int>cnt(graphmx,0);
		vector<bool>inqueue(graphmx,false);
		queue<int> q;
		dis[s] = 0;
		q.push(s);
		inqueue[s] = true;
		cnt[s]++;
		bool has_negative_cycle = false;

		while (!q.empty() && !has_negative_cycle) {
			int u = q.front();
			q.pop();
			inqueue[u] = false;

			for (int i = head[u]; i; i = edge[i].next) {
				int v = edge[i].to;
				if (dis[v] > dis[u] + edge[i].w) {
					dis[v] = dis[u] + edge[i].w;
					if (!inqueue[v]) {
						q.push(v);
						inqueue[v] = true;
						cnt[v]++;
						if (cnt[v] >= graphmx) {
							has_negative_cycle = true;
							break;
						}
					}
				}
			}
		}
		return {dis, has_negative_cycle};
	}
	pair<bool,vector<vector<int>>>Johnson() {
		memcpy(&(John.cnt),&(this->cnt),sizeof John.cnt);
		memcpy(&(John.edge),&(this->edge),sizeof John.edge);
		memcpy(&(John.head),&(this->head),sizeof John.head);
		vector<pair<int,vector<pair<int, int>>>> diss;
		for(int i=1; i<=n; i++)John.add_edge(0,i,0);
		return John.johnson();
	}

};
graph f;
void Solve() {
	cin>>n>>m;
	rep(i,1,m) {
		int u,v,w;
		cin>>u>>v>>w;
		f.add_edge(u,v,w);
	}
	pair<bool,vector<vector<int>>>a;
	a=f.Johnson();
	if(a.first) {
		cout<<"-1"<<endl;
		return;
	}
	auto b=a.second;
	rep(i,1,n) {
		int ans=0;
		for(int j=1; j<=n; j++)
			if(b[i][j]==inf) ans+=1ll*(j)*inf;
			else ans+=1ll*(j)*(b[i][j]);
		cout<<ans<<endl;

	}
}


signed main() {
	FAST();
	int T;
	T=1;
//	cin>>T;
	while(T--)Solve();
}