#include <iostream>
#include <vector>
#include <functional>
#include <limits.h>
#define MAX_N 50005

using namespace std;

vector<pair<int, int> > v[MAX_N];
int dp[MAX_N];
int dp2[MAX_N];
int main()
{
	FILE *fin = fopen("bellmanford.in", "r");
	FILE *fout = fopen("bellmanford.out", "w");
	int n, m;
	fscanf(fin, "%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		fscanf(fin, "%d %d %d", &a, &b, &c);
		a--; b--;
		v[a].push_back({b, c});
	}
	for (int i = 0; i < n; i++)
		dp[i] = INT_MAX;
	dp[0] = 0;
	
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			if (dp[i] == INT_MAX)
				continue;
			for (auto j: v[i])
				dp[j.first] = min(dp[j.first], dp[i] + j.second);
		}
	}
	for (int i = 0; i < n; i++)
		dp2[i] = dp[i];
	for (int i = 0; i < n; i++) {
		if (dp2[i] == INT_MAX)
			continue;
		for (auto j: v[i])
			dp2[j.first] = min(dp2[j.first], dp2[i] + j.second);
	}
	for (int i = 0; i < n; i++)
		if (dp2[i] != dp[i]) {
			fprintf(fout, "Ciclu negativ!\n");
			return 0;
		}

	for (int i = 1; i < n; i++)
		fprintf(fout, "%d ", dp[i]);
	fprintf(fout, "\n");

}