#include<fstream>
using namespace std;
int INF=210000000;
ifstream f("bellmanford.in");
ofstream h("bellmanford.out");
typedef struct nod{int la, cost; nod *urm;}NOD;
NOD *g[50002];
int n,m,v[50002],d[50002];
void insert(int x, int y, int c)
{
	nod *p=new nod;
	p->la=y;
	p->cost=c;
	p->urm=g[x];
	g[x]=p;
}
void citire()
{
	int i;
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		int x,y,c;
		f>>x>>y>>c;
		insert(x,y,c);
	}
}
int bmf(int start)
{
	int ap[50002],i,j,c;
	nod *st,*dr;
	for (i=1;i<=n;i++)
	{
		ap[i]=0;
		d[i]=INF;
		v[i]=0;
	}
	st=dr=new nod;
	st->la=start;
	st->urm=NULL;
	d[start]=0;
	v[start]=1;
	ap[i]++;
	while (st)
	{
		i=st->la;
		v[i]=0;
		for (nod *p=g[i];p;p=p->urm)
		{
			j=p->la;
			c=p->cost;
			if (d[j]>d[i]+c)
			{
				d[j]=d[i]+c;
				if (v[j]==0)
				{
					v[j]=1;
					if (ap[j]>n) return 0;
					ap[j]++;
					nod *t=new nod;
					t->la=j;
					t->urm=NULL;
					dr->urm=t;
					dr=dr->urm;
				}
			}
		}
		nod *t=st;
		st=st->urm;
		delete t;
	}
	return 1;
}
int main()
{
	citire();
	if (bmf(1)==0) h<<"Ciclu negativ!";
	else for (int i=2;i<=n;i++)
		h<<d[i]<<' ';
	return 0;
}