#include <stdio.h>

#define INF 50000002
#define DIM 50010

struct nod {
	int inf;
	int cost;
	nod *adr;
};

nod *V[DIM], *q;
int N, M, X, Y, C, i, j, k, ok;
int D[DIM];

int main() {
	FILE *f = fopen("bellmanford.in","r");
	FILE *g = fopen("bellmanford.out","w");
	fscanf(f,"%d %d",&N, &M);
	for (i=2;i<=N;i++) {
		D[i] = INF;
	}
	for (i=1;i<=M;i++) {
		fscanf(f,"%d %d %d",&X, &Y, &C);
		q = new nod;
		q->inf = Y;
		q->cost = C;
		q->adr = V[X];
		V[X] = q;
	}
	fclose(f);
	
	for (k = 1; k<=N; k++) {
		ok = 1;
		for (i=1;i<=N;i++) {
			for (q = V[i];q!=NULL;q = q->adr) {
				if (D[q->inf] > D[i] + q->cost) {
					D[q->inf] = D[i] + q->cost;
					ok = 0;
				}
			}
		}
	}
	
	if (ok == 0) {
		fprintf(g,"Ciclu negativ!\n");
	} else {
		for (i=2;i<=N;i++)
			fprintf(g,"%d ",D[i]);
	}
	
	return 0;
}