#include <bits/stdc++.h>
#define fir first
#define sed second
using namespace std;
const int N = 3005;
int n,m,u,v,w,cnt[N],dist[N],vis[N],t,h[N];
struct edge{
	int v,w;
};
vector<edge> e[N];
queue<int> q;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > p;
bool spfa(){
    q.push(0);
    memset(dist,0x3f,sizeof dist);
    vis[0]=1;
    dist[0]=0;
    while(q.size()){
    	int x=q.front();
    	q.pop();
    	vis[x]=0;
    	for(edge i:e[x]){
    		if(dist[i.v]>dist[x]+i.w){
    			dist[i.v]=dist[x]+i.w;
    			if(!vis[i.v]){
    				++cnt[i.v];
    				vis[i.v]=1;
    				if(cnt[i.v]>n){
    					return false;
					}
					q.push(i.v);
				}
			}
		}
	}
	return true; 
}
void dij(int s){
	memset(dist,0x3f,sizeof dist);
	dist[0]=0;
	memset(vis,0,sizeof vis);
	dist[s]=0;
	p.push(make_pair(0,s));
	while(p.size()){
		auto x=p.top();
		p.pop();
		if(vis[x.sed]) 
		    continue;
		vis[x.sed]=1;
		for(edge i:e[x.sed]){
			if(dist[i.v]>dist[x.sed]+i.w){
				dist[i.v]=dist[x.sed]+i.w;
			//	if(!vis[i.v]){
					p.push(make_pair(dist[i.v],i.v));
			//	}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		e[0].push_back({i,0});
	}
	for(int i=1;i<=m;++i){
		cin>>u>>v>>w;
		e[u].push_back({v,w}); 
	}
    if(!spfa()){
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<e[i].size();++j){
			e[i][j].w+=dist[i]-dist[e[i][j].v];
		}
	}
	for(int i=1;i<=n;++i){
		h[i]=dist[i];
	}
//	cout<<e[0].size()<<"\n";
	for(int i=1;i<=n;++i){
	    dij(i);
	    long long ans=0;
		for(int j=1;j<=n;++j){
			if(dist[j]==0x3f3f3f3f){
				ans+=j*1e9;
			}else{
				ans+=j*(dist[j]-h[i]+h[j]);
				//cout<<dist[j]-h[i]+h[j]<<" ";
			}
		}
		cout<<ans<<"\n";
	}
	return 0; 
}