#include<stdio.h>
#include<vector>
#include<queue>
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define muchii 250010
#define noduri 50010
#define max 250000000

using namespace std;

long viz[noduri];// nodul i este sau nu in coada
long d[noduri]; //distanta de la nodul de start la nodul i;
long nrfii[noduri];//numarul de fii ai nodului i;
long nrimb[noduri];//de cate ori a fost imbunatatit un nod
long n,m,ok=1;

struct nod
{
long f,c;	
};

vector<nod> lista[50001];

void read()
{
	long i,x,y,c;
	scanf("%ld %ld",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%ld %ld %ld",&x,&y,&c);
		
		nod aux;
		aux.f=y;
		aux.c=c;
		
		lista[x].push_back(aux);
		nrfii[x]++;
	}
}

void init()
{
	long i;
	for(i=1;i<=n;i++)
		d[i]=max;
	d[1]=0;
}

void belf()
{
	
	queue<long> coada;
	coada.push(1);
	viz[1]=1;
	while(!coada.empty())
	{
		int a=coada.front();
		coada.pop();
		viz[a]=0;
		for(int i=0;i<nrfii[a];i++)
		{
			int fiu=lista[a][i].f;
			int cost=lista[a][i].c;
			if(d[a]+cost< d[fiu])
			{
				d[fiu]=d[a]+cost;
				nrimb[fiu]++;
				if(nrimb[fiu]==n)
				{
					ok=0;
					return;
				}
				if(viz[fiu]==0)
				{
					coada.push(fiu);
					viz[fiu]=1;
				}
			}
		}
	}
}

void write()
{
	long i;
	if(ok==1)
		for(i=2;i<=n;i++)
			printf("%ld ",d[i]);
	else
		printf("Ciclu negativ!\n");
}
int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	read();
	init();
	belf();
	write();
	fclose(stdin);
	fclose(stdout);
	return 0;
}