#include <cstdio>
#include <vector>
using namespace std;
#define inf 10000000

struct idiot {
	int a,b,c;} e[50000];

int main ()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	int n, m, x,y;
	scanf("%d%d",&n,&m);
	vector <int> k (n+1,inf);
	for(x=1;x<=m;x++)
		scanf("%d%d%d",&e[x].a,&e[x].b,&e[x].c);
	k[1]=0;
	for(x=2;x<=n;x++)
		for(y=1;y<=m;y++)
			if(k[e[y].a]+e[y].c<k[e[y].b])
				k[e[y].b]=k[e[y].a]+e[y].c;
	for(y=1;y<=m;y++)
		if(k[e[y].a]+e[y].c<k[e[y].b]){
			printf("Ciclu negativ!\n");
			return 0;}
	for(x=2;x<=n;x++)
		printf("%d ",k[x]);
	return 0;
}