#include<fstream>
//#include<iostream.h>
#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 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()
{
	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 x)
{
	int i;
	graf *p;
	
	
	for(i=1;i<=n;i++)
	{
		d[i]=inf;
		
		
	}
	d[x]=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=1;i<=n;i++)
		g<<d[i]<<" ";
		g<<endl;
		*/
		
	}	
	
	
	//g<<endl;
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
	
	
}




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