#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define inf LLONG_MAX
using namespace std;
const int N=3e3+5;
int n,m,vis[N],cs[N];
ll h[N],dis[N];
vector<pair<int,int> > e[N];
bool spfa() {
	queue<int> q;
	q.push(0);
	memset(h,63,sizeof(h));
	h[0]=0,vis[0]=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=0; i<e[u].size(); i++) {
			int v=e[u][i].second,w=e[u][i].first;
			if(h[v]>h[u]+w) {
				h[v]=h[u]+w;
				if(!vis[v]) {
					vis[v]=1;
					q.push(v);
					cs[v]++;
					if(cs[v]>n) return 1;
				}
			}
		}
	}
	return 0;
}
void dijk(int x) {
	priority_queue<pair<int,int>> q;
	for(int i=1; i<=n; i++) dis[i]=inf;
	memset(vis,0,sizeof(vis));
	dis[x]=0;
	q.push(make_pair(0,x));
	while(!q.empty()) {
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0; i<e[u].size(); i++) {
			int v=e[u][i].second,w=e[u][i].first;
			if(dis[v]>dis[u]+w) {
				dis[v]=dis[u]+w;
				if(!vis[v]) {
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
	return;
}
int main() {
	cin>>n>>m;
	for(int i=1,u,v,w; i<=m; i++) {
		cin>>u>>v>>w;
		e[u].emplace_back(w,v);
	}
	for(int i=1; i<=n; i++) {
		e[0].emplace_back(0,i);
	}
	if(spfa()) {
		cout<<-1;
		return 0;
	}
	for(int u=1; u<=n; u++) {
		for(int i=0; i<e[u].size(); i++) {
			e[u][i].first+=h[u]-h[e[u][i].second];
		}
	}
	for(int i=1; i<=n; i++) {
		dijk(i);
		ll ans=0;
		for(ll j=1; j<=n; j++) {
			if(dis[j]==inf) {
				ans+=j*1e9;
			} else {
				ans+=j*(dis[j]+h[j]-h[i]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}