#include <stdio.h>
#include <stdlib.h>

struct muchie {
	int varfDestinatie;
	int pondere;
	struct muchie * next;
};

int INFINIT = 1 << 15;

int main() {

	FILE * in = fopen("bellmanford.in", "r");
	FILE * out = fopen("bellmanford.out", "w");

	struct muchie * v = calloc(50001, sizeof(struct muchie));
	int * drum = calloc(50001, sizeof(int));

	int n,m;
	fscanf(in, "%d%d", &n,&m);

	int i;

	for (i = 0; i < m; i++) {
		//v[i].next = NULL; 
		
		int a, b, c;
		fscanf(in, "%d%d%d", &a, &b, &c);
		
		drum[a] = INFINIT;
		drum[b] = INFINIT; 
		
		struct muchie * aux = calloc(1, sizeof(struct muchie));
		aux->varfDestinatie = b;
		aux->pondere = c;
		aux->next = v[a].next;
		v[a].next = aux;
	}

	drum[1] = 0;

	int gata = 0;
	int contor = 0; 
	while (!gata) {
		gata = 1;
		for (i = 1; i <= n; i++) {
			struct muchie * aux = v[i].next;
			while (aux) {
				//printf("%d %d %d\n",i,aux->varfDestinatie, aux->pondere);
				if (drum[aux->varfDestinatie] > drum[i] + aux->pondere) {
					drum[aux->varfDestinatie] = drum[i] + aux->pondere;
					gata = 0; 
					//printf(">>%d\n",drum[aux->varfDestinatie]);
				}
				aux = aux->next;
			}
		}
		contor++; 
		if ( contor>n){
			gata = 1; // avem un ciclu negativ garantat.
		}
	}

	if ( contor>n){
		printf("Ciclu negativ!");
	} else{
		for (i=2; i<=n; i++){
			printf("%d ",drum[i]); 
		}
	}
	
	fclose(in);
	fclose(out);

	return 0;
}