#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
#define maxn 50005
#define INF 9999999
#define maxm 250005
FILE *f=fopen("bellmanford.in","r");
FILE *g=fopen("bellmanford.out","w");
vector <pair <int,int> > G[maxm];
vector <int> dist(maxn,INF),nrcoada(maxn,0);
bitset <maxn> incoada(false);
queue <int> Q;
bool negative=false;
int n,m,x,y,c;
void bellman(){
	
	Q.push(1);
	dist[1]=0;
	incoada[1]=1;
	while(Q.empty()==0 && negative==false){
		int x=Q.front();
		Q.pop();
		incoada[x]=false;
		vector <pair <int,int> > ::iterator  Aux;
		
		for(Aux=G[x].begin();Aux!=G[x].end();Aux++)
			if(dist[x]!=INF)
				if(dist[Aux->first]>dist[x]+Aux->second)
				{
					dist[Aux->first]=dist[x]+Aux->second;
					
					if(!incoada[Aux->first])
						if(nrcoada[Aux->first]==n)
							negative=true;
						else{
							Q.push(Aux->first);
							incoada[Aux->first]=true;
							nrcoada[Aux->first]++;
						}
				}
	}	
}
int main (){
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		fscanf(f,"%d%d%d",&x,&y,&c);
		G[x].push_back(make_pair(y,c));
	}
	bellman();
	if(negative==false)
		for(int i=2;i<=n;i++)
			fprintf(g,"%d ",dist[i]);
	else
		fprintf(g,"Ciclu negativ!\n");
	return 0;
}