#include <fstream>
#include <queue>
#include <vector>
using namespace std;

#define INFINIT 10000


typedef struct _VECIN {
	int node;
	int cost;
}VECIN, *PVECIN;

int n, m;
int distanta[50002];
vector <VECIN> muchii[50002];
int contor[50002];
queue <int> noduri;



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

void BellmanFord(vector<VECIN> muchii[50002], int sursa);

int main() {
	f >> n >> m;
	int x;
	VECIN c;
	for (int i = 0; i < m; i++) {
		f >> x >> c.node >> c.cost;
		muchii[x].push_back(c);
	}
	BellmanFord(muchii, 1);

	f.close();
	q.close();
	return 0;
}

void BellmanFord(vector<VECIN> muchii[50002], int sursa) {
	
	for (int i = 0; i <= n; i++) {
		distanta[i] = INFINIT;
		contor[i] = 0;
	}

	distanta[sursa] = 0;
	noduri.push(sursa);
	contor[sursa] ++;
	bool cicluNegativ = false;
	int nodCurent;
	VECIN vc;

	while (!noduri.empty() && cicluNegativ == false) {
		nodCurent = noduri.front();
		noduri.pop();
		for (int i = 0; i < muchii[nodCurent].size(); i++) {
			vc = muchii[nodCurent][i];
			if (distanta[vc.node] > distanta[nodCurent] + vc.cost) {
				contor[vc.node]++;
				noduri.push(vc.node);
				distanta[vc.node] = distanta[nodCurent] + vc.cost;
				if (contor[vc.node] > n + 1) cicluNegativ = true;
			}
		}
	}

	if (cicluNegativ) q << "Ciclu negativ!";
	else {
		for (int i = 2; i <= n; i++) {
			q << distanta[i] << " ";
		}
	}

}