#include <iostream>
#include <fstream>
#include <vector>
#include <queue>


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

    int n, m;
    std::vector<std::vector<std::pair<int, int>>> graph;
    input >> n >> m;

    graph.resize(n + 1);

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

    std::vector<int> dist(n + 1, INT32_MAX);
    std::vector<bool> visited(n + 1, false);
    std::vector<int> appearances(n + 1, 0);
    dist[1] = 0;

    std::queue<int> queue;
    queue.push(1);
    visited[1] = true;

    bool negative_cycle = false;

    while (!queue.empty()) {
        int front = queue.front();
        queue.pop();

        visited[front] = false;

        for (const auto &x: graph[front]) {
            if (dist[x.first] > dist[front] + x.second) {
                dist[x.first] = dist[front] + x.second;
                if (!visited[x.first]) {
                    visited[x.first] = true;
                    if (appearances[x.first] > n) {
                        negative_cycle = true;
                        break;
                    }
                    appearances[x.first]++;
                    queue.push(x.first);
                }
            }
        }
    }


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

    return 0;
}