#include<fstream>
//#include<iostream.h>

#define nmax 50001
#define inf 1<<30

using namespace std;


int n,m,d[nmax],t[nmax];
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");


struct graf
{
	int nod,cost;
	graf *urm;
};

graf *gr[nmax];

void add(int x, int y, int z)
{
	graf *p;
	
	p=new graf;
	
	p->nod=y;
	p->cost=z;
	p->urm=gr[x];
	gr[x]=p;
	
	
}

/*void afisare()
{
	graf *p;
	
	for(int i=1;i<=n;i++)
	{
		cout<<i<<":";
		p=gr[i];
		while(p)
		{
			cout<<p->nod<<":"<<p->cost<<"||";
			p=p->urm;
		}
		cout<<endl;
	}
}*/

void citire()
{
	int i,x,y,z;
	f>>n>>m;
	
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>z;
		add(x,y,z);
	}
	
}

void bellmanford(int x)
{
	int i,ok;
	
	
	
	for(i=1;i<=n;i++)
	{
		d[i]=inf;
		
		
	}
	d[x]=0;
	
	
	
	for(i=1;i<=n;i++)
	{
		ok=0;
			

		graf *p=gr[i];
		
		while(p)
		{
			if(d[p->nod]>d[i]+p->cost)
			{	
				d[ p->nod ] = d[i] + p->cost;
				ok=1;	
			}
			
			p=p->urm;
		}
		
	}	
	if(ok) g<<"Ciclu negativ!";
		
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
	
	
}


int main()
{
	
	citire();
	//afisare();
	bellmanford(1);
	
	
	
return 0;
}