#include <fstream>
#include <vector>
#include <queue>
#define inf 1000000005;
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
struct much {
	vector<pair<int, int>> c;
};
vector<much> mu;
int n, m, d[50002], is[500002], prcs[50002];
int main() {
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		mu.emplace_back(much());
	}
	for (int i = 2; i <= n; i++) {
		d[i] = inf;
	}
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		cin >> x >> y >> c;
		mu[x].c.push_back({ y, c });
	}
	queue<int> qu;
	qu.push(1);
	prcs[1]++;
	is[1] = 1;
	while (qu.empty() != 1) {
		int nodact = qu.front();
		qu.pop();
		is[nodact] = 0;
		for (int i = 0; i < mu[nodact].c.size(); i++) {
			int nodnew = mu[nodact].c[i].first;
			int cost = mu[nodact].c[i].second;
			if (d[nodnew] > cost + d[nodact]) {
				d[nodnew] = cost + d[nodact];
				if (is[nodnew] == 0) {
					is[nodnew] = 1;
					qu.push(nodnew);
					prcs[nodnew]++;
					if (prcs[nodnew] == n) {
						cout << "Ciclu negativ!";
						return 0;
					}
				}
			}
		}
	}
	for (int i = 2; i < n; i++) {
		cout << d[i] << ' ';
	}
	cout << d[n];
}