#include <cstdio>
#include <climits>
#include <vector>
#include <queue>

typedef unsigned int uint;
typedef std::vector< std::vector<uint> > graph;
typedef std::vector< std::vector<int> > weightFunc;

std::vector<int> BellmanFord(graph &G,uint v,uint e,weightFunc &we,uint src)
{
	std::queue< uint > Q;

	std::vector<bool> inQ(v,false);
	std::vector<int> d(v,INT_MAX);
	std::vector<uint> l(v,0);

	d[src] = 0;
	
	Q.push( src );
	inQ[src] = true;

	while(!Q.empty())
	{
		uint c = Q.front();

		Q.pop();
		inQ[c] = false;

		if( d[ c ] < INT_MAX )
		for(uint j = 0; j < G[c].size(); ++j)
		{		
			if( d[ G[c][j] ] > d[ c ] + we[c][j] )
			{

				if(l[c] + 1 >= v)
				// in arborele creat un nod "c" nu poate fi mai jos de atat
				// decat daca "c" se gaseste pe un ciclu de cost negativ
				{
					// am gasit cel putin un ciclu negativ
					return std::vector<int>(); 
				}
				else
				{
					d [ G[c][j] ] = d[ c ] + we[c][j];
					l [ G[c][j] ] = l[ c ] + 1;

					if(!inQ[ G[c][j] ])
					{
						Q.push( G[c][j] );
						inQ[ G[c][j] ] = true;
					}
				}
			}
		}
	}

	return d;
}

int main(int,char ** argc)
{
	const char inFile[] = "bellmanford.in";
	const char outFile[] = "bellmanford.out";
	freopen(inFile,"r",stdin);
	freopen(outFile,"w",stdout);

	uint v,e;

	scanf("%u%u",&v,&e);
	
	graph G(v);
	weightFunc we(v);
	for(uint i = 0; i < e; ++i)
	{
		uint x,y;
		int w;
		scanf("%u%u%d",&x,&y,&w);
		--x; --y;
		G[x].push_back(y); we[x].push_back(w);	
	}
	std::vector<int> res = BellmanFord(G,v,e,we,0);
	if( res.empty() )
	{
		printf("Ciclu negativ!");
	}
	else
	{
		for(uint i=1;i<v;++i)
		{
			printf("%d ",res[i]);
		}
	}

	return 0;
}