#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::queue<int> Q;

    dists[src] = 0;
    for (auto i = 0u; i < G.size(); ++i)
        Q.emplace(i);

    for (auto i = 0u; i < G.size() - 1; ++i) {
        std::vector<bool> added(G.size(), false);
        bool any = false;

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

            Q.pop();
            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;
                        any = true;
                    }
                }
        }

        if (!any)
            break;
    }

    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!";
    else
        for (auto i = 1u; i < cycle.size(); ++i)
            fout << cycle[i] << " ";

    return 0;
}