#include <fstream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define IN "bellmanford.in"
#define OUT "bellmanford.out"
#define NMAX 50005
#define INF 0x3f3f3f3f

using namespace std;

//ifstream in(IN);
//ofstream out(OUT);

vector < pair<int, int> > G[NMAX];

queue <int> Q;

bool InQueue[NMAX], CicluNegativ;

int n, m, dmin[NMAX], NrViz[NMAX];

FILE *in, *out;

int main()
{
	in=fopen(IN, "r");
	out=fopen(OUT, "w");
	
	int i, a, b, c, nod, len;
	//in>>n>>m;
	fscanf(in, "%d%d", &n, &m);
	for(i=1; i<=m; ++i)
	{
		//in>>a>>b>>c;
		fscanf(in, "%d%d%d", &a, &b, &c);
		G[a].push_back(make_pair(b, c));
	}
	for(i=1; i<=n; ++i)
		dmin[i]=INF;
	Q.push(1);
	dmin[1]=false;
	InQueue[1]=true;
	while(!Q.empty() && !CicluNegativ)
	{
		nod=Q.front();
		Q.pop();
		InQueue[nod]=false;
		len=G[nod].size();
		for(i=0; i<len; ++i)
		{
			if(dmin[nod]+G[nod][i].second < dmin[G[nod][i].first])
			{
				dmin[G[nod][i].first] = dmin[nod] + G[nod][i].second;
				if(!InQueue[G[nod][i].first])
				{
					Q.push(G[nod][i].first);
					InQueue[G[nod][i].first]=true;
				}
				++NrViz[G[nod][i].first];
			}
			if(NrViz[G[nod][i].first]==n)
			{
				CicluNegativ=true;
				break;
			}
		}
	}
	if(CicluNegativ)
		//out<<"Ciclu negativ!";
		fprintf(out, "Ciclu negativ!");
	else
		for(i=2; i<=n; ++i)
			//out<<dmin[i]<<' ';
			fprintf(out, "%d ", dmin[i]);
	//out<<'\n';
	//in.close();
	//out.close();
	fclose(in);
	fclose(out);
	return 0;
}