#include <cstdio>
#define DIM 250005

const int INF = 1<<30;
struct edge
{
	int u, v, cost;
} muchii[DIM];

int n, m, d[DIM];

int main()
{
	FILE *f = fopen("bellmanford.in", "r");
	fscanf(f, "%d%d", &n, &m);
	for (int i = 1; i <= m; ++i)
		fscanf(f, "%d%d%d", &muchii[i].u, &muchii[i].v, &muchii[i].cost);
	
	fclose(f);
	
	for (int i = 2; i <= n; ++i)
		d[i] = INF;

	d[1] = 0;
	
	for (int i = 1; i <= n - 1; ++i)
		for (int j = 1; j <= m; ++j)
			if (d[muchii[j].u] + muchii[j].cost < d[muchii[j].v])
				d[muchii[j].v] = d[muchii[j].u] + muchii[j].cost;
	
	f = fopen("bellmanford.out", "w");
	int pp = 0;
	for (int i = 1; i <= m; ++i)
		if (d[muchii[i].u] + muchii[i].cost < d[muchii[i].v])
		{
			pp = 1;
			break;
		}
	
	if (!pp)
		for (int i = 2; i <= n; ++i)
			fprintf(f, "%d ", d[i]==INF?-1:d[i]);
	else
	
		fprintf (f, "Ciclu negativ!\n");
	
	fclose(f);
	
	return 0;
}