//
// Created by h4rapa1b on 11/25/25.
//
#include <fstream>
#include <vector>

using namespace std;

struct edge {
    int u, v, w;
};

const int INF = 2000000000;
int main() {
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    int n, m;
    fin >> n >> m;

    vector<edge> graph;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        fin >> u >> v >> w;
        graph.push_back({u, v, w});
    }

    // init vector de distante
    vector<int> dist(n + 1, INF);
    dist[1] = 0;

    // relaxam muchiile de n-1 ori
    for (int i = 1; i < n; ++i) {
        bool changed = false;
        for (const auto &e : graph) {
            // relaxare muchie u->v
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                changed = true;
            }
        }
        // daca nu s-au facut schimbari, iesim mai devreme
        if (!changed) {
            break;
        }
    }

    // verificare pt ciclu negativ
    bool hasNegCycle = false;
    for (const auto &e: graph) {
        // relaxare muchie u->v
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            hasNegCycle = true;
            break;
        }
    }

    if (hasNegCycle) {
        fout<<"Ciclu negativ!";
    } else {
        for (int i = 2; i <= n; ++i) {
            if (dist[i] == INF) {
                fout << 0 << " ";
            } else {
                fout << dist[i] << " ";
            }
        }
    }

    fin.close();
    fout.close();
    return 0;
}