#include <fstream>
#include <vector>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int N=50001;
const int M=250001;
const int INF=1<<30;

struct muchie{
	int x,cost;
};

vector <muchie> edge[N];
int sel[N];

int n,m,coada[M],c[N];

void citire(){
	muchie aux;
	int i,a,b,cm;
	in>>n>>m;
	for(i=1;i<=m;++i){
		in>>a>>b>>cm;
		aux.x=b;
		aux.cost=cm;
		edge[a].push_back(aux);
	}
}		

void BF(){
	int i,aux,p=0,u,a;
	u=1;
	sel[1]=1;
	coada[u]=1;
	for(i=2;i<=n;i++){
		c[i]=INF;
	}
	while(p!=u){
		p++;
		a=coada[p];
		for(i=0;i<edge[a].size();++i){
			aux=edge[a][i].x;
			if(c[a]+edge[a][i].cost<c[aux]){
				c[aux]=c[a]+edge[a][i].cost;
				if(sel[aux]>n && c[aux]<0){
					out<<"Ciclu negativ!";
					return;
				}
				sel[aux]++;
				u++;
				coada[u]=aux;
			}
		}
	}
	for(i=2;i<=n;i++){
		if(c[i]==INF){
			out<<"0\n";
			continue;
		}
		out<<c[i]<<" ";
	}	
}

int main(){
	citire();
	BF();
	return 0;
}