#include <cstdio>

#define file_in "bellmanford.in"
#define file_out "bellmanford.out"

#define nmax 250100


struct nod{
	
	int val;
	int cost;
	nod * urm;
};

nod * G[nmax];

int N,M;
int d[nmax];
int Q[nmax];
int viz[nmax];
int a,b,c;
int Nod,i;
int nr[nmax];



int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &N, &M);
	while(M--){
		scanf("%d %d %d", &a, &b, &c);
		
		nod *p=new nod;
		p->val=b;
		p->cost=c;
		p->urm=G[a];
		G[a]=p;
	}
	int p,u;
	d[1]=0;
	for (i=2;i<=N;++i)
		 d[i]=0x3f3f3f3f;
	Q[1]=1;
	viz[1]=1;
	p=1;
	u=1;
	while(p<=u){
		
		Nod=Q[p];
		viz[Nod]=0;
		nod * v;
		v=G[Nod];
		while(v){
			if (d[v->val]>d[Nod]+v->cost){
				d[v->val]=d[Nod]+v->cost;
				
				if (!viz[v->val]){
					if (nr[v->val]>N){
					printf("Ciclu negativ!\n");
					return 0;
				    }
					viz[v->val]=1;
					Q[++u]=v->val;
					nr[v->val]++;
				}
			}
		v=v->urm;
		}
	p++;
	}
	
	for (i=2;i<=N;++i)
		 if (d[i]==0x3f3f3f3f)
			 printf("0 ");
		 else
			 printf("%d ", d[i]);
		 
	return 0;

}