#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_N 1001
#define MAX_M 100001
#define INF 0x3f3f

int N,M,E[MAX_M][3],D[MAX_N],T[MAX_N];
bool OK=true;

void Bellman_Ford(int sursa)
{
	int i,j,k,c,ok,nr;
	memset(T,0,sizeof(T));
	memset(D,0x3f,sizeof(D));
	D[sursa]=0;
	
	for(ok=nr=1; ok && nr<N; nr++)
	for(ok=k=0; k<N; k++)
	{
		i=E[k][0];
		j=E[k][1];
		c=E[k][2];
		if(D[j]>D[i]+c)
		{
			D[j]=D[i]+c;
			T[j]=i;
			ok=1;
		}
	}
	
	for(k=0; k<M; k++)
	{
		i=E[k][0];
		j=E[k][1];
		c=E[k][2];
		if(D[j]>D[i]+c)
		{
			OK=false;
			break;
		}
	}
}

void Citeste(void)
{
	int i,j,k,c;
	freopen("bellmanford.in","r",stdin);
	scanf("%d %d",&N,&M);
	for(k=0; k<M; k++)
	{
		scanf("%d %d %d",&i,&j,&c);
		E[k][0]=i;
		E[k][1]=j;
		E[k][2]=c;
	}
}

void Afiseaza(void)
{
	int i;
	freopen("bellmanford.out","w",stdout);
	if(!OK)
		printf("Ciclu negativ!\n");
	else
		for(i=2; i<=N; i++)
			printf("%d ",D[i]);
}

int main()
{
	Citeste();
	Bellman_Ford(1);
	Afiseaza();

	return 0;
}