#include<stdio.h>
#include<vector>
#define inf 250000001

struct muchie
{
	int x;
	int y;
	int c;
}muchii[250001];
int lung[50001];

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	int n,m,d[50001];
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; ++i) d[i]=inf;
	for(int i=1; i<=m; ++i)
	{
		scanf("%d %d %d", &muchii[i].x,&muchii[i].y,&muchii[i].c);
		if(muchii[i].x==1) d[muchii[i].y]=muchii[i].c;
	}
	
	
	int gata=0,j,depasit=0;;
	for(j=1;j<=m&&(!gata)&&(!depasit);++j)
	{
		gata=1;
		for(int i=1; i<=m; ++i)
			if(d[muchii[i].y]>d[muchii[i].x]+muchii[i].c)  
			{
				d[muchii[i].y]=d[muchii[i].x]+muchii[i].c;
				lung[muchii[i].y]++;
				if(lung[muchii[i].y]>=n) depasit=1;
				gata=0;
			}
	}
	if(depasit && !gata ) printf("Ciclu negativ!");
	else for(int i=2; i<=n; ++i) printf("%d ",d[i]);
	return 0;
}