#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
#define FI fopen("bellmanford.in","r")
#define FO fopen("bellmanford.out","w")

struct Legatura {
	long nod;
	long cost;
	long nrUtil;
};
struct Nod {
	long cost;
	vector<Legatura> legatura;
} nod[50001];
long n;

void citeste(FILE *f) {
	long m,i,a,b,c;
	fscanf(f,"%li%li",&n,&m);
	for(i=0;i<m;i++) {
		fscanf(f,"%li%li%li",&a,&b,&c);
		nod[b].cost=nod[a].cost=0x7fffffff;
		nod[a].legatura.push_back((Legatura) {b,c,0});
	}
	nod[1].cost=0;
}

int bellman() {
	queue<long> coada;
	long front,lim,i;
	coada.push(1);
	while(!coada.empty()) {
		front=coada.front();
		coada.pop();
		lim=nod[front].legatura.size();
		for(i=0;i<lim;i++) {
			if(nod[front].cost+nod[front].legatura[i].cost<nod[nod[front].legatura[i].nod].cost) {
				nod[nod[front].legatura[i].nod].cost=nod[front].cost+nod[front].legatura[i].cost;
				nod[front].legatura[i].nrUtil++;
				if(nod[front].legatura[i].nrUtil==n)
					return 1;
				coada.push(nod[front].legatura[i].nod);
			}
		}
	}
	return 0;
}

void scrie (FILE *f) {
	int i;
	for(i=2;i<=n;i++)
		fprintf(f,"%li ",nod[i].cost);
}

int main() {
	citeste(FI);
	if(bellman())
		fprintf(FO,"Ciclu negativ!");
	else
		scrie(FO);
	return 0;
}