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

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


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

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

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

    while (i < G.size() - 1 && !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]) {
                    Q.emplace(node.first);
                    added[node.first] = true;
                }
            }
        ++i;
    }

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

    return 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 = getCycle(0, G);

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

    return 0;
}