#include <fstream>
#define MAXA 2000000000
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct Nod{int inf,c; Nod* leg;};
typedef Nod* nod;

nod a[50005],inc,sf;
int c[400005],nr[50005],n,m;
bool viz[50001];

void sterg(nod &q){viz[q->inf]=0;nod p=q->leg;delete q; q=p;}
void add(nod &q, int x,int y)
{
	nod p=new Nod;
	p->inf=x;
	p->c=y;
	p->leg=q;
	q=p;
}

void add2(int x)
{
	nr[x]++;
	viz[x]=1;
	nod p=new Nod;
	p->inf=x;
	p->leg=NULL;
	if(inc==NULL) inc=p;
	else sf->leg=p;
	sf=p;
}

int main()
{
	int i,x,y,co;
	fin>>n>>m;
	for(i=1; i<=m;i++)
	{
		fin>>x>>y>>co;add(a[x],y,co);
		c[i]=MAXA;
	}
	c[1]=0; 
	add2(1);
	while (inc)
	{
		x=inc->inf;
		sterg(inc);
		for(nod p=a[x];p;p=p->leg)
			if(c[p->inf]>c[x]+p->c)
			{
				c[p->inf]=c[x]+p->c;
				if(!viz[p->inf])
				{
					add2(p->inf);
					if(nr[x]>n){fout<<"Ciclu negativ!"; return 0;}
				}
			}
		
	}
	for(i=2; i<=n; i++) fout<<c[i]<<" ";
	return 0;
}