#include <stdio.h>
#include <queue>
#define NMAX 50005
#define MMAX 250005

using namespace std;
int N,M,cost[NMAX],ciclu=0;
typedef struct _nod{int x,c;_nod *nxt;}*L;
L muchii[NMAX];

void add(int s, int d, int c)
{
L aux=new _nod;
aux->x=d;
aux->c=c;
aux->nxt=muchii[s];
muchii[s]=aux;
}

void citire()
{
int i,x,y,c;
freopen("bellmanford.in","r",stdin);
scanf("%d %d",&N,&M);
for(i=1;i<=M;i++)
	{
	scanf("%d %d %d",&x,&y,&c);
	add(x,y,c);
	}
}

void rezolvare()
{
int incoada[NMAX],i,viz[NMAX];
queue <int>coada;

//initializam
for(i=1;i<=N;i++)
	{
	cost[i]=250000000;
	viz[i]=incoada[i]=0;
	}
coada.push(1);
cost[1]=0;
incoada[1]=1;

while(!coada.empty()&&!ciclu)
	{
	int aux=coada.front();
	coada.pop();
	incoada[aux]=0;
	viz[aux]=1;
	for(L p=muchii[aux];p;p=p->nxt)
		{
		//am obtinut un cost mai bun
		if(cost[aux]+p->c<cost[p->x])
			{
			if(viz[p->x])ciclu=1;
			//daca nu e in coada, il adaugam
			if(!incoada[p->x])
				{
				incoada[p->x]=1;
				coada.push(p->x);
				}
			cost[p->x]=cost[aux]+p->c;
			}
		}
	viz[aux]=0;
	}
}

void afisare()
{
freopen("bellmanford.out","w",stdout);
if(!ciclu)
	for(int i=2;i<=N;i++)printf("%d ",cost[i]);
else printf("Ciclu negativ!");
}

int main()
{
citire();
rezolvare();
afisare();
}