#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;


u32 n, m;

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


bool bellman (u32 start) {
    std::queue<u32> q({start});

    lengths[start] = 0;

    while (!q.empty()) {
        u32 node = q.front();
        q.pop();

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

                lengths[to] = cost + lengths[node];
                q.emplace(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!";
    }
}