#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,uint dest)
{
	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; // nivelul lui "src" e 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 [ G[c][j] ] + 1 >= v)
				{
					// 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] ] ++;

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

	return d;
}

int main(int,char ** argc)
{
	//freopen(argc[1],"r",stdin);
	//freopen(argc[2],"w",stdout);
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","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,v - 1);
	if( res.empty() )
	{
		printf("Ciclu negativ!");
	}
	else
	{
		for(uint i=1;i<v;++i)
		{
			printf("%d ",res[i]);
		}
	}

	return 0;
}