#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int n, m;
int h[N];
int dis[N], d[3005][3005];
int in[N];
bool vis[N];

int tot, head[N];

struct Node{
  int to, w, next;
}edges[N];

void add(int u, int v, int w){
  tot++;
  edges[tot].to = v;
  edges[tot].w = w;
  edges[tot].next = head[u];
  head[u] = tot;
}

void SPFA(){
	queue<int> q;
	for(int i = 1; i <= n; i++){
		h[i] = 1e9;
	}
	h[0] = 0;
	q.push(0);
	vis[0] = true;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		vis[x] = false;
		for(int i = head[x]; i; i = edges[i].next){
			if(h[x] + edges[i].w < h[edges[i].to]){
				h[edges[i].to] = h[x] + edges[i].w;
				if(!vis[edges[i].to]){
				  in[edges[i].to]++;
				  if(in[edges[i].to] > n){
				    cout << "-1";
				    exit(0);
				  }
					q.push(edges[i].to);
					vis[edges[i].to] = true;
				}
			}
		}
	}
}

void dijkstra(int s){
  memset(vis, false, sizeof(vis));
	priority_queue<pair<int, int> > q;
	for(int i = 1; i <= n; i++){
		dis[i] = 1e9;
	}
	dis[s] = 0;
	q.push(make_pair(dis[s], s));
	while(!q.empty()){
		int x = q.top().second;
		q.pop();
		if(vis[x]){
			continue;
		}
		vis[x] = true;
		for(int i = head[x]; i; i = edges[i].next){
			if(edges[i].w + dis[x] < dis[edges[i].to]){
				dis[edges[i].to] = edges[i].w + dis[x];
				q.push(make_pair(-dis[edges[i].to], edges[i].to));
			}
		}
	}
}

int main(){
  cin >> n >> m;
  for(int i = 1; i <= m; i++){
    int u, v, w;
    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 <= n; i++){
    for(int j = head[i]; j; j = edges[j].next){
      edges[j].w = edges[j].w + h[i] - h[edges[j].to];
    }
  }
  for(int i = 1; i <= n; i++){
    dijkstra(i);
    for(int j = 1; j <= n; j++){
      d[i][j] = dis[j] - h[i] + h[j];
    }
  }
  for(int i = 1; i <= n; i++){
    long long sum = 0;
    for(int j = 1; j <= n; j++){
      sum += ((long long)j * (long long)d[i][j]);
    }
    cout << sum << '\n';
  }
  return 0;
}