#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const char InFile[]="bellmanford.in";
const char OutFile[]="bellmanford.out";
const int MaxM=250010;
const int MaxN=50010;
const int INF=1<<30;

ifstream fin(InFile);
ofstream fout(OutFile);

struct to{int y,cost;};

to t;
vector<to> v[MaxN];
int N,M,q_count[MaxN],dist[MaxN];
bool is_in_q[MaxN];

bool bellmanford()
{
	for(register int i=1;i<=N;++i)
	{
		dist[i]=INF;
		q_count[i]=0;
		is_in_q[i]=false;
	}
	dist[1]=0;
	
	bool ciclu_negativ=false;

	queue<int> q;
	q.push(1);
	++q_count[1];
	is_in_q[1]=true;
	while(!q.empty())
	{
		int nod=q.front();
		q.pop();
		is_in_q[nod]=false;
		if(dist[nod]<INF)
		{
			for(register int i=0;i<(int)v[nod].size();++i)
			{
				if(v[nod][i].cost+dist[nod]<dist[v[nod][i].y])
				{
					dist[v[nod][i].y]=v[nod][i].cost+dist[nod];
					if(!is_in_q[v[nod][i].y])
					{
						if(q_count[v[nod][i].y]>N)
						{
							return false;
						}
						else
						{
							q.push(v[nod][i].y);
							is_in_q[v[nod][i].y]=true;
							++q_count[v[nod][i].y];
						}
					}
				}
			}
		}
	}
	return true;
}

int main()
{
	fin>>N>>M;
	int x,y,cost;
	for(register int i=0;i<M;++i)
	{
		fin>>x>>y>>cost;
		t.cost=cost;
		t.y=y;
		v[x].push_back(t);
	}
	fin.close();

	if(bellmanford())
	{
		for(register int i=2;i<=N;++i)
		{
			fout<<dist[i]<<" ";
		}
	}
	else
	{
		fout<<"Ciclu negativ!";
	}
	fout.close();
	return 0;
}