#include<fstream>
#include<queue>
using namespace std;

#define MAX_N 50001
#define INFINIT 100000

int n,m,d[MAX_N];

struct nod
{
	int capat,cost;
	nod *next;
}*G[MAX_N];

void add_edge(int x,int y,int c)
{
	nod *p;         p=new nod;
	p->capat=y;     p->cost=c;
	p->next=G[x];   G[x]=p;
}

void read_from_file(void)
{
	fstream f("bellmanford.in",ios::in);
	int i,x,y,c;
	f>>n>>m;
	for(i=1; i<=m; i++)
	{
		f>>x>>y>>c;
		add_edge(x,y,c);
	}
	f.close();
}

int bellman_ford(int start)
{
	int i,x,nr[MAX_N]={0};
	nod *p;  
	queue <int> C;
	for(i=2; i<=n; i++)
		d[i]=INFINIT;
	C.push(start); 
	while(!C.empty()) 
	{
		x=C.front();
		C.pop();
		
		p=G[x];
		while(p)
		{
			if(d[x]+p->cost<d[p->capat])
			{
				d[p->capat]=d[x]+p->cost;
				C.push(p->capat);
				nr[p->capat]++;
				if(nr[p->capat]==n)
					return 0;
			}
			p=p->next;
		}
	}
	return 1;
}
				
			
void write_to_file(void)
{
	fstream g("bellmanford.out",ios::out);
	int i;
	
	if(bellman_ford(1))
		for(i=2; i<=n; i++)
			g<<d[i]<<" ";
		else
			g<<"Ciclu negativ!\n";
	g.close();
}

int main()
{
	read_from_file();
	write_to_file();
	
	return 0;
}