#include<cstdio>
#include<fstream>
#define INFINIT 2100000000;
using namespace std;
struct nod{
	int capat, cost;
	nod *next;
};
nod *G[50002];
int n,m,d[50002],v[50002];
void AddArc(int x, int y, int c){
	nod *p=new nod;
	p->capat=y;
	p->cost=c;
	p->next=G[x];
	G[x]=p;
}
void citire(){
	int i;
	ifstream fin("bellmanford.in");
	fin>>n>>m;
	for(i=1;i<=m;++i){
		int x,y,c;
		fin>>x>>y>>c;
		AddArc(x,y,c);
	}
}
int bmf(int start){
	int aparitii[50002],i,j,c;
	nod *st,*dr;
	for(i=1;i<=n;++i){
		d[i]=INFINIT;
		v[i]=0;
		aparitii[i]=0;
	}
	st=dr=new nod;
	st->capat=start;
	st->next=NULL;
	d[start]=0;
	v[start]=1;
	aparitii[i]++;
	while(st){
		i=st->capat;
		v[i]=0;
		for(nod *p=G[i]; p!=NULL; p=p->next){
			j=p->capat;
			c=p->cost;
			if(d[j]>d[i]+c){
				d[j]=d[i]+c;
				if(v[j]==0){
					v[j]=1;
					if(aparitii[j]>n) 
						return 0;
					aparitii[j]++;
					nod *t=new nod;
					t->capat=j;
					t->next=NULL;
					dr->next=t;
					dr=dr->next;
				}
			}
		}
		nod *t=st;
		st=st->next;
		delete t;
	}
	return 1;
}
int main(){
	freopen("bellmanford.out","w",stdout);
	citire();
	if(bmf(1)==0)
		printf("Ciclu negativ!\n");
	else
		for(int i=2;i<=n;i++)
			printf("%d ",d[i]);
	return 0;
}