#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

#define INF 1000000000

long x[250010], y[250010], c[250010], cost[50010], n, m, i, muchie, Q1, Q2;

inline void sw(long *A) {long z = A[Q1]; A[Q1] = A[Q2]; A[Q2] = z;}

void r() {
	srand(time(NULL));
	Q1 = (rand() % m) + 1;
	//srand(time(NULL));	
	Q2 = (rand() % m) + 1;
	sw(x);
	sw(y);
	sw(c);
}

int main() {
	ifstream f("bellmanford.in");
	ofstream h("bellmanford.out");
	
	f>>n>>m;
	muchie = m;

	for (i = 1; i <= n; ++i) cost[i] = INF;
	cost[1] = 0;
	
	for (i = 1; i <= m; ++i) f>>x[i]>>y[i]>>c[i];
	
	for (i = 1; i <= 10000; ++i) r();
	
	long H = 0;
	long aux = 1;
	while (aux && H < n + 2) {
		aux = 0;
		++H;
		for (i = 1; i <= m; ++i) {
			if (cost[x[i]] + c[i] < cost[y[i]]) {
				cost[y[i]] = cost[x[i]] + c[i];
				aux = 1;
			}
		}
	}
	
	if (H == n + 2) {
		h<<"Ciclu negativ!\n";
	} else {
		for (i = 2; i <= n; ++i) {
			h<<cost[i]<<" ";
		}
	}
		
	return 0;
}