#include <stdio.h>
#include <vector>
#define DIM 50010
using namespace std;
int n, m, x, y, z, i, j, v[DIM], d[DIM], ok, k;
const int INF=(1<<30);

struct st{
	int v, c;
};

vector<st> L[DIM];
st aux;

int main(){
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for(i=2; i<=n; i++)
		d[i]=INF;
	for(i=1; i<=n; i++)
	{
		scanf("%d %d %d", &x, &y, &z);
		aux.v=y;
		aux.c=z;
		L[x].push_back(aux);
	}
	for(k=1; k<=n; k++)
	{
		ok=0;
		for(i=1; i<=n; i++)
			for(j=0; j<L[i].size(); j++)
				if(d[ L[i][j].v ]>d[i]+L[i][j].c)
				{
					d[ L[i][j].v ]=d[i]+L[i][j].c;
					ok=1;
				}
	}
	if(ok==1)
	{
		printf("Ciclu negativ!\n");
		return 0;
	}
	for(i=2; i<=n; i++)
		printf("%d ", d[i]);
	printf("\n");
	return 0;
}