#include<stdio.h>
#define MAX 50001
#define INF 0x3f3f3f3f
int n,m,i,j,d[MAX],a,b,c,X = 1,ok;
struct muchie
{
	int x,y,c;
}M[5*MAX];
int BellmanFord()
{
	for(i=ok=1;i<=n && ok;++i)
		for(j=1,ok = 0;j<=m;++j)
		{
			a = M[j].x;
			b = M[j].y;
			c = M[j].c;
			if(d[b] > d[a] + c)
			{
				d[b] = d[a] + c;
				ok = 1;
			}
		}
	for(i=1;i<=m;++i)
	{
		a = M[i].x;
		b = M[i].y;
		c = M[i].c;
		if(d[b] > d[a] + c)
			return 0;
	}
	return 1;
}
int main()
{
	FILE*f = fopen("bellmanford.in","r");
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&a,&b,&c);
		M[i].x = a;
		M[i].y = b;
		M[i].c = c;
		if(i<=n)
			d[i] = INF;
		
	}
	fclose(f);
	d[X] = 0;
	FILE*g = fopen("bellmanford.out","w");
	if(!BellmanFord())fprintf(g,"Ciclu negativ!\n");
	else
		for(i=2;i<=n;++i)
			fprintf(g,"%d ",d[i]);
	fclose(g);
	return 0;
}