#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3 * 1050;
int n,m,s;
int dist[N],dis[N],sum[N];
vector<pair<int,int> > v[N];
vector<pair<int,int> > g[N];
bool spfa(int s) {
	int vis[N];
	 memset(dist,127,sizeof(dist));
	memset(vis,0,sizeof(vis));
	memset(sum,0,sizeof(vis));
	queue<int> q;
	q.push(s);
	dist[s] = 0;
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		vis[t] = 0;
		for(int i = 0; i < v[t].size(); i ++ ) {
			int y = v[t][i].first;
			int w = v[t][i].second;
			if(dist[t] + w < dist[y]) {
				dist[y] = dist[t] + w;
				if(!vis[y]) {
					sum[y]++;
					vis[y] = 1 ;
					q.push(y);
					if(sum[y] >= n + 1) return 0;
				}
			}
		}
	}
	return 1;
}
void dij(int s){
	int vis[N];
	// memset(dist,127,sizeof(dist));
	memset(vis,0,sizeof(vis));
	priority_queue<pair<int,int> > q;
	q.push({0,s});
	dis[s] = 0;
	while(!q.empty()) {
		int t = q.top().second;
//		cout << t << " " << dis[t] << endl;
		q.pop();
		vis[t] = 1;
		for(int i = 0; i < g[t].size(); i ++ ) {
			int y = g[t][i].first;
			int w = g[t][i].second;
			if(!vis[y] && dis[t] + w < dis[y]) {
					dis[y] = dis[t] + w;
//					vis[y] ++ ;
					q.push({-dis[y],y});
//					if(vis[y] >= n + 1) return 0;
			}
		}
	}
//	return 1;
}
signed main() {
	cin >> n >> m;
	s = 1;
	for(int i = 1; i <= m; i ++ ) {
		int a,b,c;
		cin >> a >> b >> c;
		v[a].push_back({b,c});
	}
	for(int i = 1; i <= n; i++ ) {
		dist[i] = INT_MAX;
	}
	for(int s = n;s >= 1;s -- )
	if(!spfa(s)) {
		cout << -1 << endl;
		return 0;
	}
	for(int i = 1; i <= n; i ++ ) {
		for(int j = 0; j < v[i].size(); j ++ ) {
			int t = v[i][j].first;
			g[i].push_back({t,v[i][j].second + dist[i] - dist[t]});
//			cout << g[i][j].second << " " ;
		}
//		cout << endl;
	}
	for(int i = 1; i <= n; i ++ ) {
		memset(dis,127,sizeof(dis));
		int ans = 0;
		for(int j = 1;j <= n;j ++ ){
//			cout << dis[j] << " ";
		}
		dij(i);
		for(int j = 1; j <= n; j ++ ) {
//			cout << dis[j] << " ";
			if(dis[j] > 1e9) {
				ans += 1e9 * j;
//				cout << " ";
			}
			else{
				ans += j * (dis[j] + dist[j] - dist[i]);
//				cout << dis[j] + dist[j] - dist[i] << " " << ans << "  ";
			}
		}
//		cout << endl;
		cout << ans << endl;
	}
	return 0;
}