#include <algorithm>
#include <array>
#include <cstdint>
#include <fstream>
#include <iterator>
#include <queue>
#include <utility>
#include <vector>


using i32 = int32_t;
using u32 = uint32_t;

constexpr u32 MAX_NODES = 50000;
constexpr u32 MAX_EDGES = 250000;

constexpr u32 MAX_PATH  = 1000000000;


size_t n, m;

std::array<std::vector<std::pair<size_t, i32>>, MAX_NODES> edges;
std::array<i32, MAX_NODES> lengths;
std::array<size_t, MAX_NODES> viz;


bool bellman (size_t start) {
    using state_t = std::pair<size_t, i32>;
    struct comp {
        bool operator() (const state_t &a, const state_t &b) const {
            return a.second > b.second;
        }
    };
    std::priority_queue<state_t, std::vector<state_t>, comp> q;

    q.emplace(start, 0);
    lengths[start] = 0;

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

        if (lengths[node] < length)
            continue;

        for (auto [to, cost]: edges[node])
            if (lengths[to] > length + cost) {
                if (++ viz[to] == n)
                    return false;

                lengths[to] = length + cost;
                q.emplace(to, lengths[to]);
            }
    }

    return true;
}


int main () {
    std::ifstream f("bellmanford.in");
    f.exceptions(f.badbit | f.failbit | f.eofbit);
    std::ofstream g("bellmanford.out");

    f >> n >> m;

    for (u32 i = 0; i != m; ++ i) {
        u32 x, y;
        i32 z;

        f >> x >> y >> z;
        -- x, -- y;

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

    std::fill(lengths.begin(), lengths.begin() + n, MAX_PATH);

    if (bellman(0)) {
        std::copy(lengths.begin() + 1, lengths.begin() + n,
                  std::ostream_iterator<i32>(g, " "));
    } else {
        g << "Ciclu negativ!";
    }
}