# include <fstream>
# include <queue>
# define inf 1000000000
using namespace std;
ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");
queue <int> c;
int x,y,n,m,i,j,d[50005],cost,nr[50005],ok=1;
struct nod
{
	int info,cost;
	nod *urm;
}*p,*a[50005];


int main ()
{
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y>>cost;
		p=new nod;
		p->info=y;
		p->cost=cost;
		p->urm=a[x];
		a[x]=p;
	}
	for (i=2;i<=n;i++)
		d[i]=inf;
	

		c.push(1);
		while (!c.empty())
		{
			x=c.front();
			c.pop();
				
			p=a[x];
			while (p)
			{
				if (d[x]+p->cost<d[p->info])
				{
					d[p->info]=d[x]+p->cost;
					c.push(p->info);
					nr[p->info]++;
					if (nr[p->info]==n)
					{
						ok=0;
						break;
					}
				}
			p=p->urm;
			}
		if (ok==0)
			break;
		}
	

	if (ok==1)
	  for (i=2;i<=n;i++)
		g<<d[i]<<" ";
	else
		g<<"Ciclu negativ!";
	return 0;
}