#include<bits/stdc++.h>
using namespace std;
long long read(){
	long long x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void write(long long x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
	return ;
}
int n=read(),m=read();
long long INF=1000000000;
vector<pair<int,long long>> tu[3005];
long long dis[3005]; 
bool vis[3005];
int sum[3005];
long long h[3005];//虚拟节点距离其他点的距离，虚拟节点能标记负权边和负环 
bool spfa(){
	queue<int> q;
	q.push(0);
	h[0]=0;
	vis[0]=1;//在队列里
	sum[0]=1;
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		vis[u]=0;
		for(auto v:tu[u]){
			if(h[v.first]>h[u]+v.second){
				h[v.first]=h[u]+v.second;
				if(!vis[v.first]){
					vis[v.first]=1;
					q.push(v.first);
					sum[v.first]++;
					if(sum[v.first]>=n){
						return 0;
					}
				}
			}
		}
	}
	return 1;
}
void dijkstra(int s){
	priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
	pq.push({0,s});
	dis[s]=0;
	while(!pq.empty()){
		auto u=pq.top();
		pq.pop();
		if(vis[u.second]){
			continue ;
		}
		vis[u.second]=1;
		for(auto v:tu[u.second]){
			if(dis[v.first]>dis[u.second]+v.second){
				dis[v.first]=dis[u.second]+v.second;
				if(!vis[v.first]){
					pq.push({dis[v.first],v.first});
				}
			}
		}
	}
	while(!pq.empty()){
		pq.pop();
	}
}
int main(){
	for(int i=1;i<=m;i++){
		long long u=read(),v=read(),w=read();
		tu[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++){//虚拟节点对任何一个点都有一条距离为 0 的边（不是无向边）。定义虚拟节点编号为 0 
		tu[0].push_back({i,0});
	}
	memset(h,0x3f3f3f3f,sizeof(h));
	if(!spfa()){
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(auto v:tu[i]){
			tu[i][v.first].second+=h[i]-h[v.first];
		}
	}
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++){
			dis[i]=INF;
		}
		dijkstra(i);
		long long ans=0;
		for(int j=1;j<=n;j++){
			if(dis[j]==INF){
				ans+=j*INF;
			}
			else{
				ans+=j*(dis[j]+h[j]-h[i]);//处理答案的时候得减掉 
			}
		}
		write(ans); 
		puts("");
	}
	return 0;
}