#include<stdio.h>
#include<cstring>
using namespace std;
int n,m,d[50002];
char viz[50002];
int nr[50002];
#define inf 10000000

struct nod
{
	int v,c;
	nod *adresa;
};
nod *a[50002];

void adaug(int x,int y,int c)
{
	nod *p;
	p=new nod;
	p->v=y;
	p->c=c;
	p->adresa=a[x];
	a[x]=p;
}

void citire()
{
	int i,x,y,c;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		adaug(x,y,c);
	}
}

int bellmanford(int start)
{
	int i,x,y,c;
	nod *st,*ul,*p,*q;
	for(i=1;i<=n;i++)
		d[i]=inf;
	viz[start]=1;
	d[start]=0;
	st=ul=new nod;
	st->v=start;
	st->adresa=0;
	
	while(st)
	{
		x=st->v;
		viz[x]=0;
		for(p=a[x];p;p=p->adresa)
		{
			y=p->v;
			c=p->c;
			if(d[y] > d[x]+c)
			{
				d[y]=d[x]+c;
				if(viz[y]==0)
				{
					viz[y]=1;
					if(nr[y] > n)
						return 0;
					nr[y]++;
					
					q=new nod;
					q->v=y;
					q->adresa=0;
					ul->adresa=q;
					ul=ul->adresa;
				}
			}
		}
		q=st;
		st=st->adresa;
		delete q;
	}
	return 1;
}

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