#include<cstdio>
#include<iostream>
using namespace std;
#define maxn 50005
#define maxm 250005
#define maxc 1005
int t[maxm],d[maxm],e[maxn][3],n,m,s=0,ok2;
void read(){
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++)
		scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
}
void bellmanford(int x){
	d[x]=0;
	int i,j,ok,nr,c,k;
	for(ok=nr=1;nr<n && ok;nr++){
		
		
		for(ok=k=0;k<m;k++){
			i=e[k][0];
			j=e[k][1];
			c=e[k][2];
			if(c<0){
			if(d[j] > d[i]+c)
				d[j]=d[i]+c,t[j]=i,ok=1;
			}
			else{
				if(c>0) {
					if(!d[j] )
						d[j]=	maxc;
					if(d[j] > d[i]+c)
							d[j]=d[i]+c,t[j]=i,ok=1;
				}
			
					
								
			}
		}
	}		
	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();
	bellmanford(1);
	if(ok2==0)
	for(int i=2;i<=n;i++){
		cout<<d[i]<<" ";
	}
}