#include <fstream>
#include <cstdio>
#define infinit 9999999
#define nmax 50002
#define mmax 250002
using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
struct nod{
	int info,cost;
	nod *next;
};

nod *graf[nmax];
int n,m;
int viz[nmax];
int best[nmax];

void adauga(int x, int y, int c){
	nod *p=new nod;
	p->info=y;
	p->cost=c;
	p->next=graf[x];
	graf[x]=p;
}

void citire(){
	int i;
	in>>n>>m;
	for(i=1;i<=m;i++){
		int x,y,c;
		in>>x>>y>>c;
		adauga(x,y,c);
	}
}
int bmf(int start){
	int aparitii[nmax];
	int i,j,c;
	nod *prim,*ultim;
	for (i=1;i<=n;i++){
		best[i]=infinit;
		viz[i]=0;
		aparitii[i]=0;
	}
	
	prim=ultim=new nod;
	prim->info=start;
	prim->next=NULL;
	best[start]=0;
	viz[start]=1;
	aparitii[i]++;
	while (prim){
		i=prim->info;
		viz[i]=0;
		for (nod*p=graf[i]; p!=NULL; p=p->next){
			j=p->info;
			c=p->cost;
			if (best[j]>best[i]+c){
				best[j]=best[i]+c;
				if (viz[j]==0){
					viz[j]=1;
					if (aparitii[j]>n) return 0;
					aparitii[j]++;
					nod *q=new nod;
					q->info=j;
					q->next=NULL;
					ultim->next=q;
					ultim=ultim->next;
				}
			}
		}
	nod *q=prim;
	prim=prim->next;
	delete q;
	}
return 1;
}

int main(){
	citire();
	if (bmf(1)==0) {
		out<<"Ciclu negativ!"<<"\n";}else
	{
		for (int i=2;i<=n;i++)
			out<<best[i]<<" " ;
		}
		return 0;
}