#include <cstdio>
#include <cstdlib>
#include <cstring>

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

int x[250000];
int y[250000];
int c[250000];
int d[50000];

int main (int argc, char * const argv[]) {
	int n,m;
	
	fscanf(fin, "%d%d",&n,&m);
	
	memset(d,0x3f,sizeof(int)*n);
	d[0] = 0;
	
	for(int i=0; i<m; i++)
	{
		fscanf(fin, "%d%d%d",&x[i],&y[i],&c[i]);
		x[i]--; y[i]--;
	}
	
	for (int i=0; i<n-1; i++)
	{
		for (int j=0; j<m; j++)
			if (d[y[j]]>d[x[j]]+c[j])
				d[y[j]]=d[x[j]]+c[j];
	}
	
	for (int j=0; j<m; j++)
		if (d[y[j]]>d[x[j]]+c[j])
		{
			fprintf(fout, "Ciclu negativ!\n");
			fclose(fin);
			fclose(fout);
			return 0;
		}
	
	for (int i=1; i<n; i++)
		fprintf(fout, "%d ",d[i]);
	fprintf(fout, "\n");
	
	fclose(fin);
	fclose(fout);
    return 0;
}