#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define x first
#define y second
#define ppi pair<pair<int, int>, int>

const int INF = 0x3f3f3f3f;
const int MAX_N = 50010;
const int MAX_M = 250010;

int n, m;
ppi e[MAX_M];
int c[MAX_N];

int main()
{
	int i, j;
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (i = 1; i <= m; ++i)
		scanf("%d %d %d", &e[i].x.x, &e[i].x.y, &e[i].y);

	memset(c, INF, sizeof(c));
	c[1] = 0;

	for (i = 1; i <= n && i <= 15; ++i)
		for (j = 1; j <= m; ++j)
			if (c[e[j].x.x] + e[j].y < c[e[j].x.y])
				c[e[j].x.y] = c[e[j].x.x] + e[j].y;

	for (i = 1; i <= m; ++i)
		if (c[e[i].x.x] + e[i].y < c[e[i].x.y])
		{
			printf("Ciclu negativ!\n");
			return 0;
		}

	for (i = 2; i <= n; ++i)
		printf("%d ", c[i]);
}