#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;
	ok=1;
	for(nr=1;nr<n && ok;nr++){
		
		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,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();
	for(int i=1;i<=n;++i)
		d[i]=1005;
	bellmanford(1);
	if(ok2==0)
	for(int i=2;i<=n;i++){
		cout<<d[i]<<" ";
	}
}