#include <fstream>
#include <vector>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int MAXN = 50005;
const int INF = 0x3f3f3f3f;

int n, m;
struct arc {
	int from;
	int to;
	int weight;
};
vector<arc> Graph;

int pathLengthTo[MAXN];

void init(int source) {

	for (int i = 1; i <= n; i++) {
		pathLengthTo[i] = INF;
	}

	pathLengthTo[source] = 0;

}

void bellmanFord(int source = 1) {

	init(source);

	for (int looper = 1; looper < n; looper++) {
		for (arc ARC : Graph) {
			int from = ARC.from, to = ARC.to, weight = ARC.weight;

			if (pathLengthTo[from] + weight < pathLengthTo[to]) {
				pathLengthTo[to] = pathLengthTo[from] + weight;
			}
		}
	}

	for (arc ARC : Graph) {
		int from = ARC.from, to = ARC.to, weight = ARC.weight;

		if (pathLengthTo[from] + weight < pathLengthTo[to]) {
			fout << "Ciclu negativ!";
			return;
		}
	}

	for (int i = 2; i <= n; i++) {
		fout << pathLengthTo[i] << " ";
	}
}

int main() {

	fin >> n >> m;
	for (int i = 0; i < m; i++) {
		int s, d, c;
		fin >> s >> d >> c;
		Graph.push_back({ s,d,c });
	}

	bellmanFord();

	return 0;
}