#include<vector>
#include<queue>
#include<fstream>
#define inf 2000000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector< pair<int,int> > a[50001];
int d[50001],nr[50001],x,y,z,i,n,m,myn,nrc,where,what,s[50001],ok;
queue <int> c;
void citire(){
	f>>n>>m;
	for(int i=1;i<=m;i++){
		f>>x>>y>>z;
		a[x].push_back(make_pair(y,z));
	}
}
void init(){
	for(i=1;i<=n;i++)
		d[i]=inf;
	nr[1]=1;
	s[1]=1;
	d[1]=0;
	c.push(1);
	ok=1;
}
void bell()
{
   while(c.size())
   {   nrc=c.front();
	   myn=a[c.front()].size();
	   for(i=0;i<=myn-1;i++)
	   { where=a[nrc][i].first;
		 what=a[nrc][i].second;
		 if( d[nrc] + what < d[where] )
		   { d[where]=d[nrc]+what;
			 nr[where]++;
			 if(nr[where]>=n)
			 { ok=0;
			   return;
			 }
			 if(s[where]==0){
			 c.push(where);
			 s[where]=1;
			 }
		   }
	   }
	   c.pop();
	   s[nrc]=0;
   }		
}

void afisare(){		
	if(ok==0)
		g<<"Ciclu negativ!";
	else for(i=2;i<=n;i++)
		  g<<d[i]<<' ';
}
int main(){
	citire();
	init();
	bell();
	afisare();
return 0;
}