#include<fstream>
#define INF 0x3f3f3f3f
using namespace std;

typedef struct nod
{
	int inf,c;
	nod *urm;
} NOD;
typedef NOD *graf[50010];
graf G;

NOD *q,*p,*ultim,*l;
int n,m,d[50010],t[50010],cnt[50010];

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

void citire()
{
	f>>n>>m;
	int x,y,c;
	for(int i=0;i<n;i++)
	{
		f>>x>>y>>c;
		NOD *p;
		p=new NOD;
		p->urm=G[x];
		p->inf=y;
		p->c=c;
		G[x]=p;
	}
	f.close();
}
void init()
{
	d[1]=0;
	for(int i=2;i<=n;i++)
		d[i]=INF;
	q=new NOD;
	q->inf=1;
	q->urm=NULL;
	ultim=q;
	cnt[1]=1;
}
	
int main()
{
	citire();
	init();
	bool neg=false;
	while(q&&!neg)
	{
		p=G[q->inf];
		while(p&&!neg)
		{
			if(d[q->inf]+p->c<d[p->inf])
			{
				if(cnt[p->inf]>n)
					neg=true;
				else
				{
					cnt[p->inf]++;
					d[p->inf]=d[q->inf]+p->c;
					l=new NOD;
					l->inf=p->inf;
					l->urm=NULL;
					ultim->urm=l;
					ultim=l;
				}
			}
			p=p->urm;
		}
		q=q->urm;
	}
	if(neg)
		g<<"Ciclu negativ!\n";
	else
		for(int i=2;i<=n;i++)
			g<<d[i]<<' ';
	
}