#include <array>
#include <bitset>
#include <cstdint>
#include <fstream>
#include <queue>
#include <vector>
#include <utility>


using u32 = uint32_t;
using i32 = int32_t;

using graphT = std::vector<std::vector<std::pair<size_t, i32>>>;


std::vector<i32> bellman (const graphT &edges, size_t start) {
    using stateT = std::pair<size_t, i32>;
    struct minCostHeap {
        bool operator() (const stateT &a, const stateT &b) const {
            return a.second > b.second;
        }
    };

    constexpr i32 INF_PATH = 0x3fffffff;

    std::vector<size_t> viz(edges.size());
    std::vector<bool> inQ(edges.size());
    std::priority_queue<stateT, std::vector<stateT>, minCostHeap> q;
    std::vector<i32> result(edges.size(), INF_PATH);

    inQ[start] = true;
    result[start] = 0;
    q.emplace(start, result[start]);

    while (!q.empty()) {
        auto [node, pathLength] = q.top();
        q.pop();

        inQ[node] = false;

        for (auto [to, cost]: edges[node])
            if (!inQ[to] && result[to] > pathLength + cost) {
                if (++ viz[to] == edges.size())
                    return {};
                inQ[to] = true;
                result[to] = pathLength + cost;
                q.emplace(to, result[to]);
            }
    }

    return result;
}


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

    size_t nodeCount, edgeCount;
    in >> nodeCount >> edgeCount;

    graphT edges(nodeCount);

    for (size_t i = 0; i != edgeCount; ++ i) {
        size_t x, y;
        i32 cost;
        in >> x >> y >> cost;
        -- x, -- y;

        edges[x].emplace_back(y, cost);
    }

    auto result = bellman(edges, 0);

    if (result.empty()) {
        out << "Ciclu negativ!\n";
    } else {
        result.erase(result.begin());
        for (const auto &distance: result)
            out << distance << ' ';
        out << '\n';
    }
}