# include <fstream>
using namespace std;
struct nod {
	int capat, cost;
	nod *next;};
nod *g[50003];
int n, m, v[50003], ap[50003], d[50003];

void add (int i, int j, int c)
{
	nod *p=new nod;
	p->capat=j;
	p->cost=c;
	p->next=g[i];
	g[i]=p;
}

void read ()
{
	ifstream fin ("bellmanford.in");
	fin>>n>>m;
	for (;m;--m)
	{
		int x, y, c;
		fin>>x>>y>>c;
		add(x, y, c);
	}
}

struct coada {
	int i;
	coada *next;};
	
int bellman ()
{
	coada *st, *dr, *q;
	st=dr=new coada;
	int k;
	st->i=1;
	st->next=NULL;
	d[1]=0;
	v[1]=1;
	while (st)
	{
		k=st->i;
		v[k]=0;
		if (d[k]<1000000000)
		for (nod *p=g[k];p;p=p->next)
			if (d[p->capat]>d[k]+p->cost)
			{
				d[p->capat]=d[k]+p->cost;
				if (v[p->capat]==0)
				{
					if (ap[p->capat]>n)
						return 1;
					q=new coada;
					q->i=p->capat;
					q->next=NULL;
					dr->next=q;
					dr=q;
					ap[p->capat]++;
					v[p->capat]=1;
				}
			}
		q=st;
		st=st->next;
		delete q;
	}
	return 0;
}

int main ()
{
	read ();
	ofstream fout ("bellmanford.out");
	for (int i=1;i<=n;i++)
		d[i]=1000000000;
	if (bellman ())
		fout<<"Ciclu negativ!";
	else
		for (int i=2;i<=n;i++)
			fout<<d[i]<<" ";
	return 0;
}