// author: M@
#define m_
//#define _DEBUG_
#include<iostream>
#include<cstdio>
#include<string.h>
#include<iomanip>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<list>
#include<set>
#include<string>
#define clr(a)   memset((a),0,sizeof (a))


using namespace std;
typedef unsigned int ui;
typedef long long LL;
typedef pair<int,int> pii;
//const int INF=0x3f3f3f3f;
const int INF = 1e9;
const LL LINF=1e18;
const double DINF=1e9;
const double EPS=1e-9;
const int maxn=3e3 + 5;
const int maxm = 9e3 + 5;
bool vis[maxn];
int n, m, Q;
struct edg{
	int to, nxt, w;
//	edg(int a, int b, int c):to(a), nxt(b), w(c){}
}e[maxm*2];
int cnt;
int head[maxn];
void add_edg(int fx, int x, int cost){
	e[++cnt] = {x, head[fx], cost}; 
	head[fx] = cnt;
}
LL sp[maxn];
LL dst[maxn];
queue<int> sq;
int scnt[maxn];
int spfa(){
	sq.push(0);
	while(sq.empty() == false){
		int idx = sq.front();
		sq.pop();
		vis[idx] = false;
		for(int i = head[idx]; i != 0; i = e[i].nxt){
			int to = e[i].to;
			LL d = sp[idx] + e[i].w;
			if(d < sp[to]){
				sp[to] = d;
				scnt[to] = scnt[idx] + 1;
				if(scnt[to] >  n){
					return -1;
				}
				if(vis[to]) continue;
				vis[to] = true;
				sq.push(to);
			}
		}
	}
	return 0;
}

struct node{
	int to;
	LL dst;
	bool operator<(const node & a)const{
		return dst >= a.dst;
	}
};
void dij(int idx){
	priority_queue<node> dq;
	dq.push({idx, 0});
	for(int i = 1; i <=n; i++){
		vis[i] = false;
		dst[i] = INF;
	}
	dst[idx] = 0;
	while(dq.empty() == false){
		node tn = dq.top();
		dq.pop();
		if(vis[tn.to])continue;
		vis[tn.to] = true;
		for(int i = head[tn.to]; i != 0; i = e[i].nxt){
			int to = e[i].to;
			LL d = tn.dst + e[i].w;
			if(d < dst[to]){
				dst[to] = d;
				dq.push({to, d});
			}
		}
	}
}

int main()
{
#ifdef m_
    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
#endif
	scanf("%d%d", &n, &m);
	for(int i = 0 ; i < m; i++){
		int u,v,w;
		scanf("%d%d%d", &u, &v, &w);
		add_edg(u, v, w);
	}
	for(int i = 1; i <= n; i++){
		add_edg(0, i, 0);
		sp[i] = 1e9;
	}
	sp[0] = 0;
	if(spfa() == -1){
		puts("-1");
	}
	else{
		
		for(int i = 1; i <= n; i++){
			for(int j = head[i] ; j != 0; j =e[j].nxt){
				e[j].w += sp[i] - sp[e[j].to];
			}
		}
		for(int i = 1; i <= n; i++){
//			cout<<"dij"<<endl;
			LL ans = 0;
			dij(i);
			for(int j = 1; j <= n; j++){
				
				if(dst[j] == INF){
					ans += j * dst[j];
				}
				else{
					ans += j * (dst[j] - sp[i] + sp[j]);
//					printf("%d ", dst[j] - sp[i] + sp[j]);
				}
			}
			printf("%lld\n", ans);
		}
	}


	
#ifdef m_
    fclose(stdin);
//    fclose(stdout);
#endif
    return 0;
}