#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define maxn 50010
#define maxm 250010
#define inf 1000000000
#define pb push_back
#define mp make_pair

struct muchie
{
	long a, b, c;
} e[maxm];

long n, m, i, j, k, left, right, cost[maxn], f[maxn];
vector <long> v[maxn];
vector <pair<long, long> > h;

void init()
{
	long i;
	cost[1] = 0;
	for (i = 2; i <= n; i++)
		cost[i] = inf;
	h.pb(mp(0, 1));
	make_heap(h.begin(), h.end());
}

void solve()
{
	pair<long, long> per;
	long i, j, nod, poz;
	long long pas = 0;
	while (h.size() && pas <= 1LL * n * m)
	{
		pas++;
		pop_heap(h.begin(), h.end());
		per = h.back();
		h.pop_back();
		nod = per.second;
		f[nod] = 0;
		for (j = 0; j < v[nod].size(); j++)
		{
			poz = v[nod][j];
			if (cost[e[poz].a] + e[poz].c < cost[e[poz].b])
			{
				cost[e[poz].b] = cost[e[poz].a] + e[poz].c;
				if (!f[e[poz].b])
				{
					f[e[poz].b] = 1;
					h.pb(mp(-cost[e[poz].b], e[poz].b));
					push_heap(h.begin(), h.end());
				}
			}
		}
	}
}

long check_negativ()
{
	long i;
	for (i = 1; i <= m; i++)
		if (cost[e[i].a] + e[i].c < cost[e[i].b])
			return 1;
	return 0;
}

int main()
{
	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].a, &e[i].b, &e[i].c);
		v[e[i].a].pb(i);
	}
	init();
	solve();
	if (check_negativ())
	{
		printf("Ciclu negativ!\n");
		return 0;
	}
	for (i = 2; i <= n; i++)
		printf("%d ", cost[i]);
	return 0;
}