#include<stdio.h>

#define MAX  50001
#define MAX_2 250001
#define INF 2000000000

int n,m,d[MAX],viz[MAX],nr[MAX];

struct nod
{
	int inf,cost;
	nod *urm;
}*a[MAX];


struct muchie
{
	int x,y,cost;
}e[MAX_2];


int bf();


int main()
{
	nod *p;
	FILE *file=fopen("bellmanford.in","r");
	fscanf(file,"%d %d\n",&n,&m);
	for(int i=0;i<m;++i)
	{
		fscanf(file,"%d %d %d\n",&e[i].x,&e[i].y,&e[i].cost);
		p=new nod;
		p->inf=e[i].y;
		p->cost=e[i].cost;
		p->urm=a[e[i].x];
		a[e[i].x]=p;
	}
	file=fopen("bellmanford.out","w+");
	if(bf()==1)
		fprintf(file,"Ciclu negativ!");
	else
		for(int i=2; i<=n; ++i)
			fprintf(file,"%d ",d[i]);
	fprintf(file,"\n");
	return 0;
}

int bf()
{
	d[1]=0;
	int i;
	for(i=2; i<=n; ++i)
		d[i]=INF;
	int c[MAX_2];
	c[0]=1;
	int p,u;
	p=0;u=0;
	nod *q;
	while(p<=u)
	{
		for(q=a[c[p]];q!=NULL;q=q->urm)
		{
			if(d[c[p]]+q->cost<d[q->inf])
			{
				d[q->inf]=d[c[p]]+q->cost;
				if(viz[q->inf]==0)
				{	c[++u]=q->inf;
					viz[q->inf]=1;
					nr[q->inf]++;
				}
			}
			if(nr[q->inf]==n)
				return 1;
		}
		viz[c[p]]=0;
		p++;
	}
	return 0;
}