#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define MAXN 50050
#define inf 0x3fffffff

using namespace std;

struct vecin
{
    int y, cost;
    vecin(int y, int cost) : y(y), cost(cost) { }
};vector<vecin> graf[MAXN];
int n, m, inq[MAXN], times[MAXN], best[MAXN], neg;

void citire()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
        graf[x].push_back(vecin(y, z));
    }
    for (int i = 1; i <= n; i++)
		best[i] = inf;
	best[1] = 0;
}
queue<int> q;
int bellman()
{
    for (q.push(1), inq[1]=1; !q.empty(); ) {
        int top = q.front();
        q.pop();
        inq[top] = 0;
        for (vecin v : graf[top])
			if (best[top]+v.cost < best[v.y]) {
				best[v.y] = best[top]+v.cost;
                if (!inq[v.y]) {
					q.push(v.y);
					inq[v.y] = 1;
					times[v.y]++;
                    if (times[v.y] > n+2)
						return 0;
                }
			}
    }
    return 1;
}

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

	citire();
	if (!bellman())
		printf("Ciclu negativ!");
	else
		for (int i = 2; i <= n; i++)
			printf("%d ", best[i]);

    return 0;
}