# 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;
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;
	
	for (i=1;i<n;i++)
	{
		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);
				}
			p=p->urm;
			}
		}
	}
	int ok=1;
	
	for (i=1;i<=n;i++)
	{
		p=a[i];
		while (p)
		{
			if (d[i]+p->cost<d[p->info])
			{
				g<<"Ciclu negativ!";
				ok=0;
				break;
			}
			p=p->urm;
		}
		if (ok==0)
			break;
	}
	
	if (ok==1)
	for (i=2;i<=n;i++)
		g<<d[i]<<" ";
	return 0;
}