#include <fstream>
#include <vector>
#define NMAX 50001
#define MMAX 250001
using namespace std;

struct muchie
{	int x, y, c;
} L[MMAX];

const int inf=2000000000;
int D[NMAX], i, j, n, m, ok;

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

int main()
{	f>>n>>m;
	for (i=1; i<=m; ++i)
		f>>L[i].x>>L[i].y>>L[i].c;
	for (i=1; i<=n; ++i)
		D[i]=inf;
	D[1]=0;
	for (i=1; i<n; ++i)
		for (j=1; j<=m; ++j)
			if (D[L[j].y]>D[L[j].x]+L[j].c)
				D[L[j].y]=D[L[j].x]+L[j].c;
	ok=1;
	for (j=1; j<=m; ++j)
		if (D[L[j].y]>D[L[j].x]+L[j].c)
			ok=0;
	if (!ok)
		g<<"Ciclu negativ!\n";
	else
	{	for (i=2; i<=n; ++i)
			g<<D[i]<<' ';
		g<<'\n';
	}
    return 0;
}