#include<stdio.h>
#include<vector>
#include<deque>
#include<iostream>
using namespace std;

FILE *f=fopen("bellmanford.in","r");
FILE *g=fopen("bellmanford.out","w");

#define M 50001
vector<pair<long,int> >a[M];
long dist[M];
long n,m;

void cit()
{
	long i,x,y;
	int c;
	
	fscanf(f,"%ld%ld",&n,&m);
	for(i=1;i<=m;++i)
	{
		fscanf(f,"%ld%ld%d",&x,&y,&c);
		a[x].push_back(make_pair(y,c));
		
	}
	
	for(i=1;i<=n;++i)
		dist[i]=M*5;
	fclose(f);
}

int bell()
{
	deque<long> coada;
	long i,v=1;
	
	coada.push_back(1);
	dist[1]=0;

	deque<long>::iterator l;
	while(!coada.empty())
	{
		v=coada.front();
		coada.pop_front();
		
		for(i=0;i<a[v].size();++i)
			if(dist[a[v][i].first]==M*5) {dist[a[v][i].first]=dist[v]+a[v][i].second;
										  coada.push_back(a[v][i].first);}
		    else if(dist[a[v][i].first]>dist[v]+a[v][i].second) {dist[a[v][i].first]=dist[v]+a[v][i].second;
																 coada.push_back(a[v][i].first);}
	}
	
	for(i=1;i<=n;++i)
		for(v=0;v<a[i].size();++v)
			if(dist[a[i][v].first]<dist[i]+a[i][v].second) return 0;
	
	return 1;
}

void afis()
{
	long i;
	for(i=2;i<=n;++i)
		fprintf(g,"%ld ",dist[i]);
}

int main()
{
	cit();
	if(bell()) fprintf(g,"Ciclu negativ!\n");
	else afis();
	fclose(g);
	return 0;
}