#include <stdio.h>
#include <stdlib.h>

#define NMax 50005
#define MMax 250005
#define INF 50000000

FILE *fin = fopen("bellmanford.in", "rt");
FILE *fout = fopen("bellmanford.out", "wt");

int n, m;
int x[MMax], y[MMax], cost[MMax];

int d[NMax];
int *v[NMax], *co[NMax], *used[NMax]; // de cate ori am folosit muchia

void read() {
	fscanf(fin, "%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		fscanf(fin, "%d %d %d", &x[i], &y[i], &cost[i]);
		d[x[i]] ++;
	}

	for (int i = 1; i <= n; i++) {
		v[i] = (int *) malloc(d[i] * sizeof(int)); // alocare dimanica
		co[i] = (int *) malloc(d[i] * sizeof(int));
		used[i] = (int *) malloc(d[i] * sizeof(int));
		for (int j = 0; j < d[i]; j++) {
			used[i][j] = 0;
		}
		d[i] = 0;
	}

	for (int i = 0; i < m; i++) {
		// muchia x[i] -> y[i];
		// v[i][j] este al j-lea vecin al nodului i (i = Nod; j = pozitie, indexata de la 0)

		v [x[i]] [d[x[i]]] = y[i];
		co[x[i]] [d[x[i]]] = cost[i];
		d[x[i]] ++;
	}

	 // am terminat reprezentarea grafului cu liste de adiacenta, alocate dinamic
}

int dmin[NMax];
int in, sf, c[70 * NMax];

void bellmanford() {

	for (int i = 1; i <= n; i++) {
		dmin[i] = INF;
	}

	dmin[1] = 0;
	c[in] = 1;

	while (in <= sf) {
		int nod = c[in];
		in++;

		// sunt in nodul nod
		for (int i = 0; i < d[nod]; i++) {
			int newNod = v[nod][i]; // al i-lea vecin al nodului nod
			if (dmin[newNod] > dmin[nod] + co[nod][i]) {
				
				// folosesc muchia nod -> newNod

				dmin[newNod] = dmin[nod] + co[nod][i];
				used[nod][i] ++;

				if (used[nod][i] == n) {
					fprintf(fout, "Ciclu negativ!");
					fclose(fout);
					exit(0);
				}
				sf++;
				c[sf] = newNod;
			}
		}
	}
}

void write() {
	for (int i = 2; i <= n; i++) {
		fprintf(fout, "%d ", dmin[i]);
	}
	fprintf(fout, "\n");
	fclose(fout);
}

int main() {
	read();
	bellmanford();
	write();

	return 0;
}