#include<stdio.h>
#define inf 250000001

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

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<=n; ++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;
	for(j=1;j<=m&&(!gata);++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;
				gata=0;
			}
	}
	if(!gata) printf("Ciclu negativ!");
	else for(int i=2; i<=n; ++i) printf("%d ",d[i]);
	return 0;
}