#include <stdio.h>

#define INF 50000002
#define DIM 50010

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

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

struct coada {
	int inf;
	coada *adr;
};
int nrInStack[DIM], inStack[DIM];
coada *c, *p, *u;

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);
	
	
	c = new coada;
	c->inf = 1;
	c->adr = NULL;
	u = c;
	inStack[1] = 1;
	nrInStack[1] = 1;
	ok = 1;
	while (c && ok) {
		p = c;
		
		inStack[p->inf] = 0;
		for (r = V[p->inf];r!=NULL;r = r->adr) {
			if (D[r->inf] > D[p->inf] + r->cost) {
				D[r->inf] = D[p->inf] + r->cost;
				if (inStack[r->inf] == 0) {
					inStack[r->inf] = 1;
					nrInStack[r->inf]++;
					if (nrInStack[r->inf] > N)
						ok = 0;
					u->adr = new coada;
					u = u->adr;
					u->adr = NULL;
					u->inf = r->inf;
				}
			}
		}
		c = c->adr;
		delete p;
	}
	
	
	if (ok == 0) {
		fprintf(g,"Ciclu negativ!\n");
	} else {
		for (i=2;i<=N;i++)
			fprintf(g,"%d ",D[i]);
	}
	
	return 0;
}