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

using namespace std;

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

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

queue <int> Q;

bool InQueue[NMAX], NrViz[NMAX], CicluNegativ;

int n, m, dmin[NMAX];

int main()
{
	int i, a, b, c, nod, len;
	in>>n>>m;
	for(i=1; i<=m; ++i)
	{
		in>>a>>b>>c;
		G[a].push_back(make_pair(b, c));
	}
	for(i=1; i<=n; ++i)
		dmin[i]=INT_MAX;
	Q.push(1);
	dmin[1]=false;
	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);
					//++NrViz[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!";
	else
		for(i=2; i<=n; ++i)
			out<<dmin[i]<<' ';
	out<<'\n';
	in.close();
	out.close();
	return 0;
}