#include <stdio.h>

const int maxn=50001,INF=250000001;
struct nod {
	int inf,c;
	nod *next;
} *A[maxn];
int i,N,M,hp,d[maxn],nr[maxn],v[maxn],H[maxn];
void citire()
{
	int x,y,z;
	scanf("%d %d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d %d %d",&x,&y,&z);
		nod *q=new nod;
		q->inf=y;
		q->c=z;
		q->next=A[x];
		A[x]=q;
	}
}
void swap(int &a, int &b)
{
	int aux=a;
	a=b;
	b=aux;
}
void downheap(int k)
{
	int son;
	do
	{
		son=0;
		if(2*k<=hp)
		{
			son=2*k;
			if(son+1<=hp && d[H[son]]>d[H[son+1]])
				son+=1;
			if(d[H[son]]>=d[H[k]]) son=0;
		}
		if(son)
		{
			swap(H[k],H[son]);
			k=son;			
		}
	}
	while(son);
}
void upheap(int k)
{
	while(k>1 && d[H[k]]<d[H[k/2]])
	{
		swap(H[k],H[k/2]);
		k/=2;
	}
}
int radacina()
{
	int r=H[1];
	swap(H[1],H[hp]);
	hp--;
	downheap(1);
	return r;
}
void add_h(int k)
{
	H[++hp]=k;
	upheap(hp);
}
void initializari()
{
	for(i=1;i<=N;i++) d[i]=INF;
	d[1]=0; hp=0;
	add_h(1);
	for(i=1;i<=N;i++) nr[i]=0;
}

int bellman()
{
	int q;
	while(hp)
	{
		q=radacina(); //scoatem nodul cel mai apropiat
		v[q]=0; //il marcam ca scos din heap
		for(nod *x=A[q];x;x=x->next) //ii parcurgem vecinii
		{
			if(d[q]+x->c<d[x->inf]) //daca ii putem imbunatati costul
			{
				nr[x->inf]++; //marim numarul de parcurgeri al nodului
				if(nr[x->inf]>=N) return 0; //daca e depasit => ciclu negativ
				d[x->inf]=d[q]+x->c; //facem update la costul de la 1->nod
				if(v[x->inf]==0) //daca nu e in heap il introducem
				{
					v[x->inf]=1; //il marcam ca introdus
					add_h(x->inf);
				}
			}
		}
	}
	return 1;
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	citire();
	initializari();
	if(bellman())
	{
		for(i=2;i<=N;i++) printf("%d ",d[i]);
	}
	else printf("Ciclu negativ!");
}