#include<fstream>
#define dim 50002
#define inf 40000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,D[dim],x,y,c,ok,i,j;
struct {
	int x,y,c;
}
M[5*dim];
void bellman(){
	
	for(i=2;i<=n;i++)
		D[i]=inf;
	D[1]=0;
	ok=1;
	for(i=1;i<=n && ok;i++){
		
		ok=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,ok=1;
		}
		
	}
	if(ok && i==n+1)
		g<<"Ciclu negativ!";
	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[i].x=x;
		M[i].y=y;
		M[i].c=c;
	}
	bellman();
	return 0;
}