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

using WeightedGraph = std::vector<std::vector<std::pair<int, int>>>;


std::vector<int> shortestPaths(int s, const WeightedGraph &G)
{
    const int INF = 0x3f3f3f3f;

    std::vector<int> dists(G.size(), INF);
    std::vector<int> pred(G.size(), -1);

    dists[s] = 0;
    for (auto i = 0u; i < G.size() - 1; ++i)
        for (auto j = 0u; j < G.size(); ++j)
            for (auto &n : G[j])
                if (dists[n.first] > dists[j] + n.second) {
                    dists[n.first] = dists[j] + n.second;
                    pred[n.first] = j;
                }

    for (auto j = 0u; j < G.size(); ++j)
        for (auto &n : G[j])
            if (dists[n.first] > dists[j] + n.second)
                return std::vector<int>{};

    return dists;
}

std::vector<int> getCycle(int src, const WeightedGraph &G)
{
    const int INF = 0x3f3f3f3f;

    std::vector<int> dists(G.size(), INF);
    std::vector<std::size_t> count(G.size(), 0);
    std::vector<bool> added(G.size(), false);
    std::queue<int> Q;
    auto negCycle = false;

    Q.emplace(src);
    added[src] = true;
    dists[src] = 0;

    while (!negCycle && !Q.empty()) {
        auto curr = Q.front();

        Q.pop();
        added[curr] = false;
        for (auto &node : G[curr])
            if (dists[node.first] > dists[curr] + node.second) {
                dists[node.first] = dists[curr] + node.second;

                if (!added[node.first]) {
                    if (count[node.first] > G.size()) {
                        negCycle = true;
                    } else {
                        Q.emplace(node.first);
                        added[node.first] = true;
                        ++count[node.first];
                    }
                }
            }
    }

    return negCycle ? std::vector<int>{} : dists;
}

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

    int N, M;
    fin >> N >> M;

    WeightedGraph G(N);

    for (auto i = 0; i < M; ++i) {
        int x, y, w;

        fin >> x >> y >> w;
        G[x - 1].emplace_back(y - 1, w);
    }

    auto cycle = shortestPaths(0, G);

    if (!cycle.size())
        fout << "Ciclu negativ!";
    else
        for (auto i = 1u; i < cycle.size(); ++i)
            fout << cycle[i] << " ";
    fout << std::endl;

    return 0;
}