#include <stdio.h>
#include <vector>
#include <climits>

long N, M;
long long D[50001];

struct edge {
    long src;
    long dest;
    long long weight;
};

int main () {
	FILE* input = fopen("bellmanford.in", "r");
	FILE* output = fopen("bellmanford.out", "w");

	fscanf(input, "%ld %ld", &N, &M);

	//std::vector< std::vector<long> > adjList(N+1, std::vector<long>());
	std::vector<edge> edges;

	long u, v;
	long long w;
	for (long i = 0; i < M; i++) {
		fscanf(input, "%ld %ld %lld", &u, &v, &w);

		edge newEdge;
		newEdge.src = u;
		newEdge.dest = v;
		newEdge.weight = w;

		edges.push_back(newEdge);
	}

	for (long i = 2; i <= N; i++) {
		D[i] = INT_MAX;
	}

	D[1] = 0;

	for (long i = 1; i < N; i++) {
		for (long j = 0; j < M; j++) {
			//relax
			if (D[edges[j].dest] > D[edges[j].src] + edges[j].weight) {
				D[edges[j].dest] = D[edges[j].src] + edges[j].weight;
			}
		}
	}

	bool cycle = false;
	for (long j = 0; j < M; j++) {
		//relax
		if (D[edges[j].dest] > D[edges[j].src] + edges[j].weight) {
			fprintf(output, "Ciclu negativ!\n");
			cycle = true;
			break;
		}
	}

	if (!cycle) {
		for (long i = 2; i <= N; i++) {
			fprintf(output, "%lld ", D[i]);
		}
	}
	fprintf(output, "\n");

	fclose(input);
	fclose(output);

	return 0;
}