#include<fstream>
#include<vector>
#include<list>

#define NMAX 50005
#define MNAX 250005

using namespace std;

long n,m;

struct muchie
{
	long vf1,vf2,cost;
	muchie(){}
	muchie(long nvf1,long nvf2, long ncost) : vf1(nvf1), vf2(nvf2), cost(ncost){}

};

long long d[NMAX];
long pred[NMAX];
vector<muchie> E;

int main()
{
	long i,x,y,cost,j;
	fstream fin,fout;

	fin.open("bellmanford.in",ios::in);
	fout.open("bellmanford.out",ios::out);

	fin>>n>>m;

	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>cost;
		E.push_back(muchie(x,y,cost));
	}
	d[1]=0;

	for(i=2;i<=n;i++)
		d[i]=LONG_MAX;

	for(i=1;i<n;i++)
		for(j=0;j<m;j++)
			if(E[j].cost+d[E[j].vf1]<d[E[j].vf2])
			{
				pred[E[j].vf2]=E[j].vf1;
				d[E[j].vf2]=E[j].cost+d[E[j].vf1];
			}

	int ok=1;
	for(i=0;i<m && ok==1;i++)
	{
		if(d[E[i].vf2]>d[E[i].vf1]+E[i].cost)
			ok=0;
	}

	if(ok==0)
		fout<<"Ciclu negativ!";
	else
		for(i=2;i<=n;i++)
			fout<<d[i]<<" ";
	fout<<'\n';

	fin.close();
	fout.close();
	return 0;
}