#include<stdio.h>
using namespace std;
#define maxn 50005
#define maxm 250005
#define maxx 9000000000
long long int t[maxn],d[maxn],e[maxm][3],n,m,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]);
		if(i<=n)
			d[i]=maxx;
	}
}
void bellmanford(int x){
	d[x]=0;
	int k,i,j,c,ok,nr;
	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(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!"),k=m,ok2=1;
	}
}
int main (){
	read();
	bellmanford(1);
	if(ok2==0)
		for(int i=2;i<=n;i++)
			printf("%lld ",d[i]);
	return 0;
}