#include<fstream.h>
#include<iostream.h>

int n,m,i,x,start[50100],v[250100][3],U,c[50100],u,d[50100],nr,ok,o,pus[50100],w,t,cc[50100],ww;

int main()
{
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>v[i][0]>>v[i][2];
		v[i][1]=start[x];
		start[x]=i;
	}
	U=(1<<30);
	u=1;
	c[1]=1;
	for(i=2;i<=n;i++)
		d[i]=U;
	nr=1;
	while(u&&nr<n)
	{
		for(i=1;i<=n;i++)
			pus[i]=0;
		ok=0;
		o=0;
		for(i=1;i<=u;i++)
		{
			w=c[i];
			t=start[w];
			while(t)
			{
				ww=v[t][0];
				if(d[w]+v[t][2]<d[ww])
				{
					d[ww]=d[w]+v[t][2];
					if(!pus[ww])
					{
						pus[ww]=1;
						cc[++o]=ww;
					}
				}
				t=v[t][1];
			}
		}
		for(i=1;i<=o;i++)
			c[i]=cc[i];
		u=o;
		nr++;
	}
	for(i=1;i<=u;i++)
	{
		w=c[i];
		t=start[w];
		while(t)
		{
			if(d[w]+v[t][2]<d[v[t][0]])
			{
				g<<"Ciclu negativ!";
				return 0;
			}
			t=v[t][1];
		}
	}
	for(i=2;i<=n;i++)
		g<<d[i]<<' ';
	return 0;
}