#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
#define MAX_N 50010
#define INF 0x3f3f3f3f

typedef pair <int,int> hh;
vector <hh> nr[MAX_N];
int n,m,dist[MAX_N],CN,scos[MAX_N];
void solve(){
	int x;
	queue <int> Q;
	vector <bool> inQ(MAX_N,false);
	Q.push(1);
	inQ[1]=true;
	while(!Q.empty() && !CN){
		x=Q.front();
		Q.pop();
		inQ[x]=false;
		for(vector <hh>::iterator it=nr[x].begin();it!=nr[x].end();++it){
			if(dist[it->first] > dist[x]+it->second){
				dist[it->first]=dist[x]+it->second;
				if(!inQ[it->first])
					if(scos[it->first]>n)
						CN=1;
					else{
						inQ[it->first]=true;
						++scos[it->first];
						Q.push(it->first);
					}
			}
		}
	}
}
int main(){
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	int i,a,b,c;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;++i){
		scanf("%d%d%d",&a,&b,&c);
		nr[a].push_back(hh(b,c));
	}
	for(i=2;i<=n;++i)
		dist[i]=INF;
	solve();
	
	if(CN)
		printf("Ciclu negativ!\n");
	else{
		for(i=2;i<=n;++i)
			printf("%d ",dist[i]);
		printf("\n");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}