#include <stdio.h>

struct nod
{
	int nr,c;
	nod *adr;
} *graf[50005],*u;
int n,m,i,x,y,z,s[50005],q[50005],st,dr,d[50005],heap[50005],root,poz[50005],aux,min,j,step;
long long prod;
bool k;

inline void heap_up(int p)
{
	while (p>1 && d[heap[p]]<d[heap[p/2]])
	{
		aux=heap[p];
		heap[p]=heap[p/2];
		heap[p/2]=aux;
		poz[heap[p]]=p;
		poz[heap[p/2]]=p/2;
		p/=2;
	}
}

inline void heap_down(int p)
{
	while ((p*2<=x && d[heap[p]]>d[heap[p*2]]) || (p*2+1<=x && d[heap[p]]>d[heap[p*2+1]]))
	{
		if (p*2+1<=x)
			if (d[heap[p*2]]<d[heap[p*2+1]])
				min=p*2;
			else
				min=p*2+1;
		else
			min=p*2;
		aux=heap[p];
		heap[p]=heap[min];
		heap[min]=aux;
		poz[heap[p]]=p;
		poz[heap[min]]=min;
		p=min;
	}
}	

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d",&x,&y,&z);
		u=new nod;
		u->nr=y;
		u->c=z;
		u->adr=graf[x];
		graf[x]=u;
	}
	d[1]=0;
	for (i=2;i<=n;++i)
		d[i]=250000000;
	x=1;
	heap[1]=1;
	poz[1]=1;
	prod=1LL*n*m+2;
	for (step=1;x && step<=prod;++step)
	{
		root=heap[1];
		poz[root]=0;
		--x;
		if (x)
		{
			heap[1]=heap[x+1];
			poz[heap[1]]=1;
			heap_down(1);
		}
		for (u=graf[root];u;u=u->adr)
			if (d[root]+u->c<d[u->nr])
			{
				d[u->nr]=d[root]+u->c;
				if (poz[u->nr])
					heap_up(poz[u->nr]);
				else
				{
					heap[++x]=u->nr;
					heap_up(x);
				}
			}
	}
	if (x)
		printf("Ciclu negativ!");
	else
		for (i=2;i<=n;++i)
			printf("%d ",d[i]);
	return 0;
}