#include <fstream>
#include <queue>
using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

struct MUCHIE
{
	int a,b,c;
};

int n,m,i,j,c[50010];
MUCHIE g[250010];

int main()
{
	in>>n>>m;
	for(i=1; i<=m; i++)
		in>>g[i].a>>g[i].b>>g[i].c;
	
	for(i=2; i<=n; i++)
		c[i] = 1<<29;
	
	for(i=1; i<=n; i++)
		for(j=1; j<=m; j++)
			if(c[g[j].a] + g[j].c < c[g[j].b])
				c[g[j].b] = c[g[j].a] + g[j].c;
			
	for(i=2; i<=m; i++)
		if(c[g[i].a]+g[i].c < c[g[i].b])
			{out<<"Ciclu negativ!";return 0;}
			
	for(i=2; i<=n; i++)
		out<<c[i]<<' ';
	
	return 0;
}