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

using namespace std;

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

bool bellford(int node) {
    queue<int> Q;
    D[node] = 0;
    Q.push(node);
    C[node]++;
    while(!Q.empty()) {
        int cur_node = Q.front();
        Q.pop();
        if(C[cur_node] > N) {
            return false;
        }
        for(auto neigh : G[cur_node]) {
            if(D[neigh.first] > D[cur_node] + neigh.second) {
                D[neigh.first] = D[cur_node] + neigh.second;
                Q.push(neigh.first);
                C[neigh.first]++;
            }
        }
    }

    return true;
}

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

    scanf("%d %d", &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, z;
        scanf("%d %d %d", &x, &y, &z);

        G[x].push_back({y, z});
    }

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

    return 0;
}