#include <iostream>

const int MAX_N = 50000;
const int MAX_M = 250000;
const int INF = 1e9;

struct Edge {
    int u, v, c;

    void read() {
        std::cin >> u >> v >> c;
    }
};

int n, m;
Edge edges[MAX_M];
int d[MAX_N + 1];

void read_edges() {
    for (int i = 0; i < m; i++) {
        edges[i].read();
    }
}

// returns true if it was actually relaxed
bool relax_edge(Edge e) {
    if (d[e.u] + e.c < d[e.v]) {
        d[e.v] = d[e.u] + e.c;
        return true;
    } else {
        return false;
    }
}

// returns true if there is a negative cycle
bool bellman_ford() {
    bool any = false;
    d[1] = 0;

    for (int i = 0; i < n; i++) {
        any = false;

        for (int j = 0; j < m; j++) {
            any |= relax_edge(edges[j]);
        }
    }

    return any;
}

void print_distances() {
    for (int i = 2; i <= n; i++) {
        std::cout << d[i] << ' ';
    }
}

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

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n >> m;
    read_edges();
    std::fill(d, d + MAX_N + 1, INF);

    if (bellman_ford()) {
        std::cout << "Ciclu negativ!";
    } else {
        print_distances();
    }
}