#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 2000000000

using namespace std;

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

int n, m;

vector <int> v;
queue <int> coada;

vector < pair<int, int> > graf[50005];

int d[50005];
int viz[50005];
int esteincoada[50005];

bool bellmanford(int s) {
	for (int i = 1; i <= n; i++) {
		viz[i] = 0;
		esteincoada[i] = 0;
		d[i] = INF;
	}
	d[s] = 0;
	coada.push(s);
	esteincoada[s] = 1;
	while (!coada.empty()) {
		int nodcurent = coada.front();
		viz[nodcurent]++;
		if (viz[nodcurent] >= n)
			return false;
		coada.pop();
		esteincoada[nodcurent] = 0;
		for (int i = 0; i < graf[nodcurent].size(); i++) {
			int vecin = graf[nodcurent].first;
			int cost = graf[nodcurent].second;
			if (d[nodcurent] + cost < d[vecin]) {
				d[vecin] = d[nodcurent] + cost;
				if (!esteincoada[vecin])
					coada.push(vecin);
			}
		}
	}
	return true;
}

int main()
{
	in >> n >> m;
	for (int i = 1; i <= n; i++) {
		int x, y, c;
		in >> x >> y >> c;
		graf[x].push_back(make_pair(y, c));
	}
	if (bellmanford(1)) {
		for (int i = 2; i <= n; i++)
			out << d[i] << " ";
	}
	else {
		out << "Ciclu negativ!";
	}
}