#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=3e3+5;
#define int long long
vector<pair<int,int>> g[N];
const int inf=1e9;
int d[N],inv[N];
int h[N];
bool vs[N];
void dij(int s){
	memset(vs,0,sizeof(vs));
	for(int i=1;i<=n;i++)d[i]=inf;
	d[s]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int> > > q;
	q.push({d[s],s});
	while(q.size()){
		auto T=q.top();
		int u=T.first;q.pop();
		if(vs[u])continue;
		vs[u]=1;
		for(auto G:g[u]){
			int v=G.first,w=G.second;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				q.push({d[v],v}); 
			}
		}
	} 
}
signed main(){
	cin>>n>>m;
	
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++){
		h[i]=inf;
	}
	for(int i=1;i<=n;i++){
		g[0].push_back({i,0}); 
	}
	h[0]=0;
	vs[0]=1;
	queue<int> q;
	q.push(0);
	while(q.size()){
		int u =q.front();q.pop() ;
		vs[u]=0;
		for(auto G:g[u]){
			int v=G.first,w=G.second;
			if(h[v]>h[u]+w){
				h[v]=h[u]+w;
				if(!vs[v]){
					vs[v]=1;
					q.push(v);
					inv[v]++;
					if(inv[v]>n+1){
						puts("-1");
						return 0;
					}
				}
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=0;j<(long long)g[i].size();j++){
			g[i][j].second+=h[i]-h[g[i][j].first];
		}
	}	
	for(int i=1;i<=n;i++){
		dij(i);
		long long ans=0;
		for(int j=1;j<=n;j++){
			if(d[j]==inf){
				ans+=1ll*j*inf;
			}else{
				ans+=1ll*j*(d[j]+h[j]-h[i]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}