#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define dim 50005
vector <pair <int,int> > v[dim];
int viz[dim], d[dim], use[dim], n, m,ok;
queue <int> q;

void read()
{
	int i, a, b, c;
	fin>>n >>m;
	for(i=1;i<=m;++i)
	{
		fin>>a >>b >>c;
		v[a].pb(mp(b,c));
	}
}

void solve()
{
	vector <pair <int,int> > ::iterator it;
	memset(d,inf,sizeof(d));
	int nod;
	q.push(1);
	d[1]=0;
	use[1]=1;
	
	while(!q.empty())
	{
		nod=q.front();
		viz[nod]=0;
		for(it=v[nod].begin();it!=v[nod].end();++it)
		{
			if(d[nod]+it->sc < d[it->fs])
			{
				d[it->fs]= d[nod]+it->sc;
				
				if(viz[it->fs]==0)
				{
					viz[it->fs]=1;
					q.push(it->fs);
				}
				if(++use[it->fs]==n)
				{
					ok=1;
					return ;
				}
			}
		}
		
		q.pop();
	}
}

void print()
{
	if(ok==1)
		fout<<"Ciclu negativ";
	else
		for(int i=2;i<=n;++i)
			fout<<d[i] <<" ";
}

int main()
{
	read();
	solve();
	print();
	
	return 0;
}