#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N=3e4+5;
const int M=6e4+5;

int n,m,u,v,w;
struct node{
	int fr,to,next,wei;
}e[M<<1];
int k,pre[M<<1];
inline void add(int fr,int to ,int va){
	k++;
	e[k].fr=fr;
	e[k].to=to;
	e[k].wei=va;
	e[k].next=pre[fr];
	pre[fr]=k;
	return ;
}
bool vis[N];
ll h[N],dis[N];
int cnt[N];
inline void spfa(){
	for(int i=0;i<=n;i++){
		//cout<<"??\n";
		h[i]=1e12;
	} 
	queue<int> q;
	q.push(0);
	h[0]=0;
	vis[0]=true;
	while(!q.empty()){
		int head=q.front();
		q.pop();
		vis[head]=false;
		for(int i=pre[head];i!=0;i=e[i].next){
			//cout<<head<<' '<<e[i].to<<' '<<e[i].wei+h[head]<<' '<<h[e[i].to]<<endl;
			if(e[i].wei+h[head]<h[e[i].to]){
				h[e[i].to]=e[i].wei+h[head];
				cnt[e[i].to]=cnt[head]+1;
				if(cnt[e[i].to]>n){
					puts("-1\n");
					exit(0);
				}
				if(!vis[e[i].to]){
					q.push(e[i].to);
					vis[e[i].to]=true;
				}
			}
		}
	}
}

inline void diji(int s){
	priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int>> > q;
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=n;i++) dis[i]=1e12;
	dis[s]=0;
	q.push({0,s});
	while(!q.empty()){
		int head=q.top().second,di=q.top().first;
		q.pop();
		if(vis[head]) continue;
		vis[head]=true;
		for(int i=pre[head];i!=0;i=e[i].next){
			//cout<<head<<' '<<e[i].to<<' '<<di+e[i].wei<<' '<<dis[e[i].to]<<endl;
			if(di+e[i].wei<dis[e[i].to]){
				dis[e[i].to]=di+e[i].wei;
				q.push({dis[e[i].to],e[i].to});
			}
		}
	}
}

signed main(){
//	freopen("P5905_3.in","r",stdin);
//	freopen("zsq.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	for(int i=1;i<=n;i++) add(0,i,0);
	spfa();
	for(int i=1;i<=k;i++){
		//cout<<h[e[i].fr]<<' '<<h[e[i].to]<<endl; 
		if(e[i].fr==0) continue;
		e[i].wei+=h[e[i].fr]-h[e[i].to];
		//cout<<e[i].fr<<' '<<e[i].to<<' '<<e[i].wei<<endl;
	} 
//	diji(1);
//	for(int i=1;i<=n;i++) cout<<dis[i]<<endl;
	for(int i=1;i<=n;i++){
		diji(i);
		ll ans=0;
		for(int j=1;j<=n;j++){
			if(dis[j]>=1e12) ans+=(ll)j*1000000000;
			if(i==j) continue;
			else ans+=(ll)j*(dis[j]+h[j]-h[i]);
			//cout<<i<<' '<<j<<' '<<dis[j]+h[j]-h[i]<<endl;
		}
		cout<<ans<<endl;
	}
	return 0;
}