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

#define mp make_pair
#define pb push_back
#define x first
#define y second
#define ppi pair<pair<int, int>, int>
#define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
#define ll long long

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

int n, m, z;
ppi e[MAX_M];
int c[MAX_N], f[MAX_N], q[MAX_N];
vector <int> v[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);
		v[e[i].x.x].pb(i);
	}

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

	for (i = 1; i <= z && i <= (ll)n * m; ++i)
	{
		int nod = q[i % n];
		f[nod] = 0;

		forit(it, v[nod])
			if (c[e[*it].x.x] + e[*it].y < c[e[*it].x.y])
			{
				c[e[*it].x.y] = c[e[*it].x.x] + e[*it].y;

				if (!f[e[*it].x.y])
				{
					f[e[*it].x.y] = 1;
					++z;
					q[z % n] = e[*it].x.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]);
}