#include<fstream>
#include<vector>
#include<list>
#include<iostream>
#include<queue>

#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;
vector<list<muchie> > V;
int main()
{
	long i,x,y,cost;
	fstream fin,fout;
	queue<muchie> Q;

	fin.open("bellmanford.in",ios::in);
	fout.open("bellmanford.out",ios::out);
	list<muchie> lista;

	fin>>n>>m;

	for(i=0;i<=n;i++)
	{
		d[i]=LONG_MAX;
		V.push_back(lista);
	}
	d[1]=0;

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

	for(i=1;i<n;i++)
	{
		
		cout<<i<<'\n';
		list<muchie>::iterator itr;
		for(itr=V[i].begin(); itr!=V[i].end(); itr++)
			Q.push(*itr);
		
		while(!Q.empty())
		{
			muchie mn=Q.front();
			Q.pop();
			if(mn.cost+d[mn.vf1]<d[mn.vf2])
			{
				pred[mn.vf2]=mn.vf1;
				d[mn.vf2]=mn.cost+d[mn.vf1];
				for(itr=V[mn.vf2].begin(); itr!=V[mn.vf2].end(); itr++)
					Q.push(*itr);
			}
		}
	}
	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;
}