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

#define NMAX 50005
#define MMAX 250005

using namespace std;

long n,m;
long nrUtilizariMuchie[MMAX];
struct muchie
{
	long vf1,vf2,cost,loc;
	muchie(){}
	muchie(long nvf1,long nvf2, long ncost, long nloc) : vf1(nvf1), vf2(nvf2), cost(ncost), loc(nloc){}

};

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

			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=1;i<=n && ok==1;i++)
	{
		for(itr=V[i].begin(); itr!=V[i].end(); itr++)
			if(d[(*itr).vf2]>d[(*itr).vf1]+(*itr).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;
}