#include<fstream>
using namespace std;
int n,m,d[50005],in_stiva[50005],cont[50005];
const int inf=1<<30;
struct muchie
{
	int u,v,cost;
};
muchie much[250005];
typedef
struct stiva
{
	int nr;
	stiva*urm;
}*Pstiva;
Pstiva stiv[50005],vf;
short sw;
int main()
{
	ifstream fin("bellmanford.in");
	fin>>n>>m;
	int i,x,j;
	for(i=1;i<=m;i++)
		fin>>much[i].u>>much[i].v>>much[i].cost;
	for(i=1;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	Pstiva p;
	p=new(stiva);
	p->nr=1;
	p->urm=vf;
	vf=p;
	in_stiva[1]=1;
	while(vf&&sw==0)
	{
		x=vf->nr;
		vf=vf->urm;
		in_stiva[x]=0;
		//for(i=1;i<=n-1;i++)
			for(j=1;j<=m;j++)
				if(d[much[j].u]<inf)
				if(d[much[j].v]>d[much[j].u]+much[j].cost)
				{
					d[much[j].v]=d[much[j].u]+much[j].cost;
					if(in_stiva[much[j].v]==0)
					{
						if(cont[much[j].v]>n)
							sw=1;
					    else
						{
							p=new(stiva);
							p->nr=much[j].v;
							p->urm=vf;
							vf=p;
							in_stiva[much[j].v]=1;
							cont[much[j].v]++;
						}
						
					}
				}
    }				
	ofstream fout("bellmanford.out");
	if(sw==1)
		fout<<"Ciclu negativ!\n";
	else
		{for(i=2;i<=n;i++)
			fout<<d[i]<<" ";
	fout<<'\n';
		}
		fin.close();
		fout.close();
		return 0;
}