#include <bits/stdc++.h>
using namespace std;
long long const INF = 1e9;
long long n, m;
long long a[3100][3100];

int main() {
	cin >> n >> m;
	for (long long i = 1; i <= n; i++) {
		for (long long j = 1; j <= n; j++) {
			if (i == j) {
				a[i][j] = 0;
			} else {
				a[i][j] = INF;
			}
		}
	}
	for (long long i = 0; i < m; i++) {
		long long u, v, w;
		cin >> u >> v >> w;
		if (a[u][v] > w) {
			a[u][v] = w;
		}
	}
	for (long long k = 1; k <= n; k++) {
		for (long long i = 1; i <= n; i++) {
			for (long long j = 1; j <= n; j++) {
				if (a[i][k] != INF && a[k][j] != INF) {
					if (a[i][j] > a[i][k] + a[k][j]) {
						a[i][j] = a[i][k] + a[k][j];
					}
				}
			}
		}
	}
	bool b = false;
	for (long long i = 1; i <= n && !b; i++) {
		if (a[i][i] < 0) {
			b = true;
		}
	}
	if (b) {
		cout << -1 << endl;
	} else {
		for (long long i = 1; i <= n; i++) {
			long long sum = 0;
			for (long long j = 1; j <= n; j++) {
				if (a[i][j] == INF) {
					sum += j * 1e9;
				} else {
					sum += j * a[i][j];
				}
			}
			cout << sum << endl;
		}
	}

	return 0;
}