#include<fstream>
#include<queue>

#define nmax 50001
#define inf 1<<30

using namespace std;


int n,m,d[nmax],t[nmax];
queue <int> c;

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 citire()
{
	ifstream f("bellmanford.in");
	
	
	int i,x,y,z;
	f>>n>>m;
	
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>z;
		add(x,y,z);
	}
	f.close();
}

int bellmanford()
{
	int i,x;
	graf *p;
	
	
	for(i=1;i<=n;i++)	
		d[i]=inf;		
	
	d[1]=0;
	
	c.push(1);
	
	while(!c.empty())
	{		
		x=c.front();
		c.pop();
		p=gr[x];		
		while(p)
		{
			if(d[p->nod]>d[x]+p->cost)
			{	
				d[ p->nod ] = d[x] + p->cost;				
				c.push(p->nod);
				t[p->nod]++;
				if (t[p->nod]==n)
				{  
					g<<"Ciclu negativ!";
					return 0;
				}
					
			}
			
			p=p->urm;
		}
	
	}	
	
	
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
	g.close();
	return 1;
}




int main()
{
	
	citire();	
	bellmanford();		
	
return 0;
}