#include<fstream>
using namespace std;
int n,m,d[50005],in_stiva[50005],cont[50005];
const int inf=1<<30;
typedef
struct nod
{
	int v,cost;
	nod*ur;
}*Pnod;
Pnod l[500005];
//muchie much[250005];
typedef
struct stiva
{
	int nr;
	stiva*urm;
}*Pstiva;
Pstiva stiv[50005],vf;
short sw;
int main()
{
	ifstream fin("bellmanford.in");
	fin>>n>>m;
	int i,x,j,a,b,cst;
	Pnod q;
	for(i=1;i<=m;i++)
		{
			fin>>a>>b>>cst;
			q=new(nod);
			q->v=b;
			q->cost=cst;
			q->ur=l[a];
			l[a]=q;
	}
	for(i=1;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	Pstiva p;
	p=new(stiva);
	p->nr=1;
	p->urm=vf;
	vf=p;
	in_stiva[1]=1;
	cont[1]=1;
	Pnod r;
	while(vf&&sw==0)
	{
		x=vf->nr;
		vf=vf->urm;
		in_stiva[x]=0;
		//for(i=1;i<=n-1;i++)
			for(r=l[x];r!=NULL&&sw==0;r=r->ur)
			   if(d[x]<inf)
				if(d[r->v]>d[x]+r->cost)
				{
					d[r->v]=d[x]+r->cost;
					if(!in_stiva[r->v])
					{
						p=new(stiva);
							p->nr=r->v;
							p->urm=vf;
							vf=p;
						in_stiva[r->v]=1;
							cont[r->v]++;
						if(cont[r->v]>n)
							sw=1;
					    
					}
				}
    }				
	ofstream fout("bellmanford.out");
	if(sw==1)
		fout<<"Ciclu negativ!\n";
	else
		{for(i=2;i<=n;i++)
			fout<<d[i]<<" ";
	fout<<'\n';
		}
		fin.close();
		fout.close();
		return 0;
}