#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define pi std::pair<int,int>

const int nmax = 5e4 + 5;
const int inf = 1e9;

int d[nmax], f[nmax];
std::vector<pi>l[nmax];
std::queue<int>q;

int main() {
	std::ifstream fin("bellmanford.in");
	std::ofstream fout("bellmanford.out");
	int n, m, u, v, c;
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		fin >> u >> v >> c;
		l[u].push_back({ v, c });
	}
	for (int i = 1; i <= n; i++) d[i] = inf;
	q.push(1), d[1] = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		f[x]++;
		if (f[x] >= n) {
			fout << "Ciclu negativ!\n";
			return 0;
		}
		for (auto y : l[x])
			if (d[x] + y.second < d[y.first])
				q.push(y.first), d[y.first] = d[x] + y.second;
	}
	for (int i = 2; i <= n; i++) fout << d[i] << " ";
}