#include<fstream>
#include<vector>
#define NMAX 50002
#define inf 40000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int D[NMAX],n,i,j,x,y,c,N,M,a;
struct muchii{  
	int x,y,c;
}
m[250008];
void init(){
	D[1]=0;
	for(int i=2;i<=N;i++){
		D[i]=inf;
	}
}
void rez(){
	int i,j,check=1;
	for(i=1;i<=N && check;++i){
		check=0;
		for(j=1;j<=M;++j)
			if(D[m[j].y]>D[m[j].x]+m[j].c){
				D[m[j].y]=D[m[j].x]+m[j].c;
				check=1;
			}
	}
	if(check && i==N+1)
		g<<"Ciclu negativ!"<<"\n";
	else
		for(i=2;i<=N;i++)
		    g<<D[i]<<" ";
}
int main (){
	f>>N>>M;
	for(i=1;i<=M;i++){
		f>>x>>y>>c;
		m[++a].x=x;
		m[a].y=y;
		m[a].c=c;
	}
	init();
	rez();
	return 0;
}