#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int inf = 2e9;

int n, m;
vii gf[100001];
bool inqueue[100001];
queue<ii> q;
int d[100001], qn[100001];

bool spfa(int s) {
	for (int i = 1; i <= n; i++)
		d[i] = inf;
	d[s] = 0;
	q.push({ d[s], s });
	inqueue[s] = 1;
	while (!q.empty()) {
		int vn = q.front().second;
		q.pop();
		inqueue[vn] = 0;
		for (ii i : gf[vn]) {
			int vvc = i.first;
			int vvn = i.second;
			if (d[vvn] > d[vn] + vvc) {
				d[vvn] = d[vn] + vvc;
				if (!inqueue[vvn]) {
					qn[vvn]++;
					if (qn[vvn] > n - 1)
						return 0;
					q.push({ d[vvn], vvn });
					inqueue[vvn] = 1;
				}
			}
		}
	}
	return 1;
}

int main() {
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		fin >> x >> y >> c;
		gf[x].push_back({c, y});
	}
	if (spfa(1))
		for (int i = 2; i <= n; i++)
			fout << d[i] << " ";
	else
		fout << "Ciclu negativ!";
	return 0;
}