#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;
	}


	int gata = 0;
	int contor = 0; 
	
	int * q = calloc(50000,sizeof(int)); 
	int * pus = calloc(50001,sizeof(int)); 
	int * ctr = calloc(50001,sizeof(int)); 
	int stanga = 0; 
	int dreapta = 0; 
	drum[1] = 0;
	//dreapta++; 
	q[dreapta] = 1; 
	pus[1] = 1; 
	ctr[1]++;
	while ( stanga<=dreapta) {
	
		int varfCurrent = q[stanga]; 
		pus[varfCurrent]=0; 
		stanga++;  
		stanga = stanga%50000; 
		
			struct muchie * aux = v[varfCurrent].next;
			while (aux) {
				//printf("%d %d %d\n",varfCurrent,aux->varfDestinatie, aux->pondere);
				if (drum[aux->varfDestinatie] > drum[i] + aux->pondere) {
					drum[aux->varfDestinatie] = drum[i] + aux->pondere;
					if (!pus[aux->varfDestinatie]){
						dreapta++; 
						dreapta = dreapta % 50000; 
						q[dreapta] = aux->varfDestinatie;
						pus[aux->varfDestinatie] = 1; 
						ctr[aux->varfDestinatie]++; 
						if ( ctr[aux->varfDestinatie]>n){
							contor=n+1; 
							stanga = dreapta+1; // iesim din bucla mare
							break; 
						}
					}
				}
				aux = aux->next;
			}
		
	}

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

	return 0;
}