#include <iostream>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

struct way {
    int x, y, c;
};

int N, M;
vector<vector<way>> G;
vector<int> D, C;

bool bellman(int node) {
    queue<int> Q;
    Q.push(node);
    D[node] = 0;
    C[node]++;
    while(!Q.empty()) {
        int node = Q.front();
        Q.pop();

        if(C[node] > N) {
            return false;
        }

        for(auto way : G[node]) {
            if(D[way.y] > D[node] + way.c) {
                D[way.y] = D[node] + way.c;
                Q.push(way.y);
                C[way.y]++;
            }
        }
    }

    return true;
}

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

    cin >> N >> M;

    G.resize(N + 1);
    D.resize(N + 1);
    C.resize(N + 1);
    fill(D.begin(), D.end(), INT_MAX);
    fill(C.begin(), C.end(), 0);

    for(int i = 1; i <= M; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        way drum;
        drum.x = x;
        drum.y = y;
        drum.c = c;

        G[x].push_back(drum);
    }

    if(bellman(1)) {
        for(int i = 2; i <= N; i++) {
            printf("%d ", D[i]);
        }
    } else {
        printf("Ciclu negativ!\n");
    }

    return 0;
}