#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;

void BellmanFord_r(uint c,graph &G,weightFunc &we,std::vector<int> & d)
{
	static std::vector<bool> vis(G.size());

	vis[c] = true;

	for(uint j = 0; !d.empty() && j < G[c].size(); ++j)
	{
		if( d[ G[c][j] ] > d[ c ] + we[c][j] )
		{
			if(vis[ G[c][j] ]) //am gasit un ciclu de cost negativ
			{
				d.clear();
			}
			else
			{
				d [ G[c][j] ] = d[ c ] + we[c][j];
				BellmanFord_r(G[c][j],G,we,d);
			}
		}
	}

	vis[c] = false;
}

std::vector<int> BellmanFord(graph &G,weightFunc &we,uint src)
{
	uint v = G.size();
	std::vector<int> d(v,INT_MAX);
	d[src] = 0;
	BellmanFord_r(0,G,we,d);
	return d;
}

int main(int,char ** argc)
{
	const char inFile[] = "grader_test1.in";
	const char outFile[] = "grader_test1.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,we,0);
	if( res.empty() )
	{
		printf("Ciclu negativ!");
	}
	else
	{
		for(uint i=1;i<v;++i)
		{
			printf("%d ",res[i]);
		}
	}

	return 0;
}