#include<fstream>
#define in 1<<20
#define nm 50005
using namespace std;
ofstream g("bellmanford.out");

struct lista
{
	int inf,c;
	lista *nod;
} *t[nm];
int i,j,n,m,v[nm],c[nm],d[nm],uz[nm],x,y,cost;
void add(int i,int j,int cost)
{
	lista *p;
	p=new lista;
	p->inf=j;
	p->c=cost;
	p->nod=t[i];
	t[i]=p;
}
int ciclu()
{
	int i,nod,st,dr;
	lista *p;
	for(i=1;i<=n;i++)
		d[i]=in;
	st=dr=1;
	uz[st]=1;
	d[st]=0;
	v[st]=1;
	c[st]=1;
	while(st<=dr)
	{
		nod=c[st];
		v[nod]=0;
		for(p=t[nod];p;p=p->nod)
			if(d[p->inf]>d[nod]+(p->c))
			{
				d[p->inf]=d[nod]+(p->c);
				if(!v[p->inf])
				{
					v[p->inf]=1;
					c[++dr]=p->inf;
					++uz[p->inf];
					if(uz[p->inf]>n)
						return 1;
				}
			}
			++st;
	}
	return 0;
}
int main()
{
	ifstream f("bellmanford.in");
	lista *p;
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>cost;
		add(x,y,cost);
	}
	if(ciclu())
		g<<"Ciclu negativ";
	else
		for(i=2;i<=n;i++)
			if(d[i]==in)
				g<<0<<" ";
			else
				g<<d[i]<<" ";
			return 0;
}