#include<cstdio>
#include<algorithm>]
#include<queue>
#define INF 100000
using namespace std;
//ifstream f("bellmanford.in");
//ofstream g("bellmanford.out");
int d[50001], incoada[50001];
queue<int> c;
struct pizza
{
	int x, y, v;
}a[250001];
bool cmp(pizza a, pizza b)
{
	if (a.x < b.x)
		return 1;
	return 0;
}
int main()
{
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	int i, p, u, x;
	long long cnt = 0, n, m;
	scanf("%lld %lld", &n, &m);
	for (i = 1; i <= m; i++)
		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].v);
	sort(&a[1], &a[m + 1], cmp);
	for (i = 1; i <= n; i++)
		d[i] = INF;
	p = u = 1;
	c.push(1);
	incoada[1] = 1;
	d[1] = 0;
	while (!c.empty() && cnt <= n*m)
	{
		cnt++;
		x = c.front();
		c.pop();
		incoada[x] = 0;
		i = 1;
		while (a[i].x < x)i++;
		for (; a[i].x == x; i++)
		{
			if (d[x] + a[i].v < d[a[i].y])
			{
				d[a[i].y] = d[x] + a[i].v;
				if (!incoada[a[i].y])
				{
					c.push(a[i].y);
					incoada[a[i].y] = 1;
				}
			}
		}
	}
	if (cnt == n *m + 1)
		printf("Ciclu negativ!");
	else
		for (i = 2; i <= n; i++)
			printf("%d ", d[i]);
}