#include<cstdio>
using namespace std;
#define maxn 50005
#define maxm 250005
#define maxx 0x7ffffff
long long int e[maxm][3],d[maxm],t[maxm],n,m,ok2;
void read(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%lld %lld",&n,&m);
    for(int i=0;i<m;i++){
		if(i>=1 && i<=n)
			d[i]=maxx;
        scanf("%lld%lld%lld",&e[i][0],&e[i][1],&e[i][2]);
	}
}
void bellman(int x){
	d[x]=0;
	long long int ok=1,i,j,c,k,nr;
	for(nr=1;nr<n && ok;++i){
		ok=0;
		for(k=0;k<m;++k){
			i=e[k][0];
			j=e[k][1];
			c=e[k][2];
			if(d[j]>d[i]+c)
				d[j]=d[i]+c,ok=1,t[j]=i;
		}
	}
		for(k=0;k<m;++k){
			i=e[k][0];
			j=e[k][1];
			c=e[k][2];
			if(d[j]>d[i]+c){
				printf("Ciclu negativ!\n"),k=m,ok2=1;
			}
		}
}
int main(){
	read();
	bellman(1);
	if(!ok2)
		for(int i=2;i<=n;++i)
			if(d[i]!=maxx)
			printf("%lld ",d[i]);
	return 0;
}