#include <iostream>
#include <fstream>
#include <vector>
#include <climits>

struct Edge {
    int start = 0, finish = 0, weight = 0;

    Edge(int start, int finish, int weight) {
        this->start = start;
        this->finish = finish;
        this->weight = weight;
    }

    Edge() = default;
};

int main() {
    std::ifstream input("bellmanford.in");
    std::ofstream output("bellmanford.out");

    int n, m;
    input >> n >> m;

    std::vector<Edge> edges;
    for (int i = 0; i < m; ++i) {
        int x, y, t;
        input >> x >> y >> t;
        edges.emplace_back(x, y, t);
    }

    std::vector<long long> dist(n + 1, LLONG_MAX);
    dist[1] = 0;

    for (int i = 1; i < n; ++i) {
        for (const Edge& e : edges) {
            if (dist[e.start] != LLONG_MAX && dist[e.finish] > dist[e.start] + e.weight) {
                dist[e.finish] = dist[e.start] + e.weight;
            }
        }
    }

    bool negative_cycle = false;
    for (const Edge& e : edges) {
        if (dist[e.start] != LLONG_MAX && dist[e.finish] > dist[e.start] + e.weight) {
            negative_cycle = true;
            break;
        }
    }

    if (negative_cycle) {
        output << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= n; ++i) {
            output << dist[i] << " ";
        }
    }

    input.close();
    output.close();
    return 0;
}