#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;
    std::vector<Edge> edges;
    input >> n >> m;

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

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

    for (int i = 1; i <= n - 1; ++i) {
        for (int j = 0; j < m; ++j) {
            int u = edges[j].start;
            int v = edges[j].finish;
            int weight = edges[j].weight;
            if (dist[u] != INT_MAX && dist[v] > dist[u] + weight) dist[v] = dist[u] + weight;
        }
    }

    bool negative_cycle = false;

    for (int j = 0; j < m; ++j) {
        int u = edges[j].start;
        int v = edges[j].finish;
        int weight = edges[j].weight;

        if (dist[u] != INT_MAX && dist[v] > dist[u] + weight) {
            negative_cycle = true;
            break;
        }
    }

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

    return 0;
}