#include <fstream>
#define MAXN 999999999
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct Nod{int inf,c; Nod* leg;};
typedef Nod* nod;

nod a[50001],inc1,sf1;
int viz[50001],cost[50001],numar[50001],n,m,inc,sf;
//unsigned short q[800001];

void add(int x, int y,int co)
{
	nod p=new Nod;
	p->inf=y;
	p->c=co;
	p->leg=a[x];
	a[x]=p;
}

int main()
{
	int x,y,c,i;
	fin>>n>>m;
	for(i=1; i<=m; i++)
	{
		fin>>x>>y>>c;
		add(x,y,c);
		cost[i]=MAXN;
	}
	nod p=new Nod; p->inf=1;p->leg=NULL;inc1=p;sf1=p;
	cost[1]=0;
	viz[1]=1;
	numar[1]=1;
	//inc=1;sf=1;
	//q[1]=1;
	while (inc1/*inc<=sf*/)
	{
		for(nod p=a[inc1->inf/*q[inc]*/];p;p=p->leg)
			if(cost[p->inf]>cost[inc1->inf]+p->c)
			{
				cost[p->inf]=cost[inc1->inf]+p->c;
				if(!viz[p->inf])
				{
					nod q=new Nod; q->inf=p->inf; q->leg=NULL; sf1->leg=q;sf1=q;
					//sf++;q[sf]=p->inf;
					viz[p->inf]=1;
					numar[p->inf]++;
				}
				if(numar[p->inf]>n){fout<<"Ciclu negativ!"; return 0;}
			}
		viz[inc1->inf]=0;
		//inc++;
		nod q=inc1->leg;
		delete inc1;
		inc1=q;
	}
	for(i=2; i<=n; i++) fout<<cost[i]<<" ";
	return 0;
}