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

using namespace std;

vector<int> vecini[50001];
vector<int> costuri[50001];
vector<int> coada;
vector<int> coada2;

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