#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e9;
int cnt,n,m,head[5010],sum[5010],diss[5010],disd[5010];
bool vis[5010];
struct qedge{
	int to,nextt,quan;
}edge[10010];
void addedge(int x,int y,int z){
	edge[++cnt].to = y;
	edge[cnt].quan = z;
	edge[cnt].nextt = head[x];
	head[x] = cnt;
}
queue<int> q;
bool spfa(int x){
	for(int i = 1;i <= n;i++) diss[i] = inf;
	q.push(x);
	diss[x] = 0;
	vis[x] = 1; 
	sum[x]++;
	while(!q.empty()){
		int u = q.front();
		vis[u] = 0;
		q.pop();
		for(int i = head[u];i;i = edge[i].nextt){
			int v = edge[i].to;
			if(diss[v] > diss[u] + edge[i].quan){
				diss[v] = diss[u] + edge[i].quan;
				if(!vis[v]){
					q.push(v);
					vis[v] = 1;
					sum[v]++;
					if(sum[v] == n + 1) return true;
				}
			}
		}
	} 
	return false;
}
struct node{
	int id,dis;
	bool operator < (const node &x)const{
		return x.dis < dis; 
	} 
}; 
priority_queue<node> qq;
void dijkstra(int x){
	int u;
	for(int i = 1;i <= n;i++) disd[i] = inf,vis[i] = 0;
	disd[x] = 0;
	qq.push((node){x,0});
	vis[x] = 1;
	while(!q.empty()){
		node temp = qq.top();
		u = temp.id;
		q.pop();
		if(!vis[u]){
			vis[u] = 1;
			for(int i = head[u];i;i = edge[i].nextt){
				int v = edge[i].to;
				if(disd[v] > disd[u] + edge[i].quan){
					disd[v] = disd[u] + edge[i].quan;
					if(!vis[v]){
						qq.push((node){v,disd[v]});
					}
				}
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		addedge(a,b,c);
	}
	for(int i = 1;i <= n;i++){
		addedge(0,i,0);
	}
	if(spfa(0)){
		cout<<-1;
		return 0;	
	}
	for(int u = 1;u <= n;u++){
		for(int i = head[u];i;i = edge[i].nextt){
			edge[i].quan = diss[u] - diss[edge[i].to];
		}
	}
	for(int i = 1;i <= n;i++){
		memset(disd, inf, sizeof(disd));
		memset(vis, false, sizeof(vis));
		dijkstra(i);
		long long ans = 0;
		for(int j = 1;j <= n;j++){
			if(disd[j] == inf){
				ans += j * inf;
			}
			else {
				ans += j * (disd[j] + diss[j] - diss[i]);
			}
		}
		cout<<ans<<endl;
		ans = 0;
	}
}