#include <cstdio>
#include <list>
#include <limits>
using namespace std;

#define NMAX 50000
#define COST_MAX 1000
struct edge { int from, to, cost; };

int N, M;
list<edge> edges;
int distances[NMAX+1];

void readInput() {
	int from, to, cost;
	freopen("bellmanford.in","r",stdin);
	scanf("%d %d",&N,&M);
	for (int i=0;i<M;i++) {
		scanf("%d %d %d",&from,&to,&cost);
		edge new_edge = {from, to, cost};
		edges.push_back(new_edge);
	}	
}

bool bellman_ford(int s) {
	int i;
	for (i=1;i<=N;i++) {
		distances[i] = COST_MAX+1;
	}
	distances[s] = 0;
	for (i=1;i<N;i++) {
		for (list<edge>::iterator it = edges.begin();it!=edges.end();it++) {
			int to = ((edge)*it).to, from = ((edge)*it).from, cost = ((edge)*it).cost;
			if (distances[to] > distances[from]+cost) {
				distances[to] = distances[from]+cost;
			}
		}
	}
	for (list<edge>::iterator it = edges.begin();it!=edges.end();it++) {
		if (distances[((edge)*it).to] > distances[((edge)*it).from]+((edge)*it).cost) {
			return false;
		}
	}
	return true;
}

int main() {
	readInput();	
	freopen("bellmanford.out","w",stdout);
	if (bellman_ford(1)) {
		for (int i=2;i<=N;i++) {
			printf("%d ",distances[i]);
		}
	}
	else {
		printf("Ciclu negativ!");
	}
	printf("\n");
	return 0;
}