#include <stdio.h>
#include <vector>
#include <queue>
#define y first
#define c second
#define pb push_back
#define mp make_pair
#define INF 2147000000
using namespace std;

#define Nmax 50005

vector< pair< int,int > > G[Nmax];
vector< pair< int,int > >:: iterator it;
queue< int > Q;

int inq[Nmax],cnt[Nmax],d[Nmax];
int n,m,i,ciclu_negativ;
int x,y,z;

int main(){
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		G[x].pb(mp(y,z));
	}
	
	for(i=2;i<=n;++i) d[i]=INF;
	Q.push(1);
	
	while( !Q.empty() && !ciclu_negativ){
		x=Q.front();
		
		for(it=G[x].begin(); it!=G[x].end(); ++it)
			if( d[it->y] > d[x] + it->c ){
				d[it->y] = d[x] + it->c;
				if( cnt[it->y] > n-1 ){
					ciclu_negativ=1;
					break;
				}
				if( !inq[it->y] ){
					inq[it->y]=1;
					Q.push(it->y);
					cnt[it->y]++;
				}
			}
		
		inq[x]=0;
		Q.pop();
	}
	
	if(ciclu_negativ) printf("Ciclu negativ!");
	else 
		for(i=2;i<=n;++i) printf("%d ",d[i]);
	printf("\n");
		
	fclose(stdin); fclose(stdout);
	return 0;
}