#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;
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;
	}
	k=true;
	for (i=1;i<=n;++i)
	{
		s[i]=i;
		q[1]=i;
		for (j=1;j<=n;++j)
			d[j]=250000000;
		d[i]=0;
		for (st=dr=1;st<=dr && k;++st)
			for (u=graf[q[st]];u && k;u=u->adr)
				if (s[u->nr]==i)
				{
					if (u->nr==i && d[q[st]]+u->c<0)
					{
						k=false;
						break;
					}
				}
				else
				{
					s[u->nr]=i;
					q[++dr]=u->nr;
					d[u->nr]=d[q[st]]+u->c;
				}
	}
	if (!k)
	{
		printf("Ciclu negativ!");
		return 0;
	}
	d[1]=0;
	for (i=2;i<=n;++i)
		d[i]=250000000;
	x=1;
	heap[1]=1;
	poz[1]=1;
	while (x)
	{
		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);
				}
			}
	}
	for (i=2;i<=n;++i)
		printf("%d ",d[i]);
	return 0;
}