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

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

std::vector<int> shortestPaths(int src,
                               const WeightedGraph &Gmin,
                               const WeightedGraph &Gplus)
{
    const int INF = 0x3f3f3f3f;

    std::vector<int> dists(Gmin.size(), INF);
    std::vector<std::size_t> count(Gmin.size(), 0);
    std::vector<bool> added(Gmin.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 it = Gplus[curr].cbegin(); it != Gplus[curr].cend(); ++it)
            if (dists[it->first] > dists[curr] + it->second) {
                dists[it->first] = dists[curr] + it->second;

                if (!added[it->first]) {
                    if (count[it->first] > Gmin.size()/2) {
                        negCycle = true;
                    } else {
                        Q.emplace(it->first);
                        added[it->first] = true;
                        ++count[it->first];
                    }
                }
            }

        for (auto it = Gmin[curr].cbegin(); it != Gmin[curr].cend(); ++it)
            if (dists[it->first] > dists[curr] + it->second) {
                dists[it->first] = dists[curr] + it->second;

                if (!added[it->first]) {
                    if (count[it->first] > Gmin.size()/2) {
                        negCycle = true;
                    } else {
                        Q.emplace(it->first);
                        added[it->first] = true;
                        ++count[it->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 Gmin(N);
    WeightedGraph Gplus(N);

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

        fin >> x >> y >> w;
        if (x < y)
            Gplus[x - 1].emplace_back(y - 1, w);
        else
            Gmin[x - 1].emplace_back(y - 1, w);
    }

    auto lessCmp = [](const std::pair<int, int> &lhs,
                      const std::pair<int, int> &rhs) {
        return lhs.second < rhs.second;
    };
    auto greaterCmp = [](const std::pair<int, int> &lhs,
                         const std::pair<int, int> &rhs) {
        return lhs.second > rhs.second;
    };
    for (auto i = 0; i < N; i++) {
        std::sort(Gplus[i].begin(), Gplus[i].end(), lessCmp);
        std::sort(Gmin[i].begin(), Gmin[i].end(), greaterCmp);
    }

    auto cycle = shortestPaths(0, Gmin, Gplus);

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

    return 0;
}