#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);
	std::vector<int> d(v);

	for(uint i = 0;i < v; ++i)
	{
		d[i] = INT_MAX;
	}

	Q.push(src);
	inQ[src] = true;
	
	d[src] = 0;
	
	for(uint i = 0;i < v - 1; ++i)
	{
		uint c = Q.front();
		Q.pop();
		inQ[c] = false;

		for(uint j = 0; j < G[c].size(); ++j)
		{
			if( d[ G[c][j] ] > d[ c ] + we[c][j] )
			{
				d [ G[c][j] ] = d[ c ] + we[c][j];
				if(G[c][j] != dest)
				{
					Q.push( G[c][j] );
					inQ[ G[c][j] ] = true;
				}
			}
		}
	}
	// daca mai sunt elemente in coada inseamna ca
	// s-a gasit cel putin un ciclu de cost negativ
	if(!Q.empty())
	{	
		d.clear();
	}

	return d;
}

int main()
{
	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(int i=1;i<v;++i)
		{
			printf("%d ",res[i]);
		}
	}

	return 0;
}