#include<fstream>
#include<queue>
#include<cstdlib>
using namespace std;
int n,m,x0=1; 
int d[50050];
struct Nod{int x,c;};
Nod *G[50050],aux;
bool aparitie[50050],ciclu;
int ordin[50050];

void Citire()
{
	int i,x,y,c;
	ifstream fin("bellmanford.in");
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		G[i]=(Nod *)realloc(G[i],sizeof(Nod));
		G[i][0].x=G[i][0].c=0;
	}
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		aux.x=y;
		aux.c=c;
		G[x][0].x++;
		G[x]=(Nod *)realloc(G[x],(G[x][0].x+1)*sizeof(Nod));
		G[x][G[x][0].x]=aux;
	}
	fin.close();
}


int Bellman_Ford()
{
	int i,x;
	for(i=1;i<=n;i++)
		d[i]=2000000000;
	d[x0]=0;
	queue <int> Q;
	Q.push(x0);
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		aparitie[x]=false;
		for(i=1;i<=G[x][0].x;i++)
		{
			aux=G[x][i];
			if(d[aux.x]>d[x]+aux.c)
			{
				d[aux.x]=d[x]+aux.c;
				if(aparitie[aux.x]==false)
				{
					if(ordin[aux.x]>n)
					{
						return 1;
					}
					else
					{
						Q.push(aux.x);
						aparitie[aux.x]=true;
						ordin[aux.x]=ordin[x]+1;
					}
				}
				
			}
		}
	}
	return 0;
}

void Afisare()
{
	int i;
	ofstream fout("bellmanford.out");
	if(ciclu==true)
		fout<<"Ciclu negativ!"<<"\n";
	else
	{
		for(i=2;i<=n;i++)
		{
			fout<<d[i]<<' ';
		}
		fout<<"\n";
	}
	fout.close();
}

int main()
{	
	Citire();
	ciclu=Bellman_Ford();
	Afisare();
	return 0;
}