code:

#include<bits/stdc++.h>
#define V (int)(5e3+3)
#define E (int)(1e4+3)
#define INF (int)(1e9+0)
using namespace std;
struct edge{int nxt,to,w;}h[E];
int n,m,s,tot,ans,head[V],high[V],dis[V],vis[V],cnt[V];
queue<int>Q;
void add(int u,int v,int w){
	h[++tot].nxt=head[u];
	h[tot].to=v;
	h[tot].w=w;
	head[u]=tot;
}
bool SPFA(int s){
	memset(high,0x3f,sizeof(high));
	high[s]=0;
	vis[s]=1;
	Q.push(s);
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=h[i].nxt){
			int y=h[i].to;
			if(high[y]>high[x]+h[i].w){
				high[y]=high[x]+h[i].w;
				if(!vis[y]){
					vis[y]=1;
					Q.push(y);
					++cnt[y];
					if(cnt[y]==n+1) return 0;
				}
			}
		}
	}
	return 1;
}
struct node{
	int dis,id;
	bool operator<(const node&a)const{return dis>a.dis;}
    node(int d,int x){dis=d,id=x;}
};
void Dijkstra(int s){
	priority_queue<node>pQ;
	for(int i=1;i<=n;++i) dis[i]=INF;
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	pQ.push(node(0,s));
	while(!pQ.empty()){
		int x=pQ.top().id;
		pQ.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=h[i].nxt){
			int y=h[i].to;
			if(dis[y]>dis[x]+h[i].w){
				dis[y]=dis[x]+h[i].w;
				if(!vis[y]) pQ.push(node(dis[y],y));
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
    s=n+1;
	while(m--){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
    for(int i=1;i<=n;++i) add(n+1,i,0);
	if(!SPFA(n+1)){puts("-1");return 0;}
	for(int i=1;i<=n;++i) for(int j=head[i];j;j=h[j].nxt) h[j].w+=high[i]-high[h[j].to];
	for(int i=1;i<=n;++i){
		Dijkstra(i);
		ans=0;
		for(int j=1;j<=n;++i){
			if(dis[j]==INF) ans+=j*INF;
			else ans+=j*(dis[j]+high[j]-high[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}