#include <fstream>
#include <iostream>
#include <queue>

using namespace std;
using Graph = vector<vector<pair<int, int> > >;


vector<int> getBestWay(int source, const Graph& G)
{
    const int Inf = 0x3f3f3f3f;

    vector<bool> inQueue(G.size(), false);
    vector<size_t> count(G.size(), 0);
    vector<int> distances(G.size(), Inf);
    queue<int> Q;
    auto negCycle = false;

    Q.emplace(source);
    inQueue[source] = true;
    distances[source] = 0;

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

        Q.pop();
        inQueue[currNode] = false;
        for (auto &node : G[currNode])
            if (distances[node.first] > distances[currNode] + node.second) {
                distances[node.first] = distances[currNode] + node.second;

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

    return negCycle ? vector<int>{} : distances;
}

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

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

    Graph G(N + 1);

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

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

    auto bestWay = getBestWay(1, G);

    if (!bestWay.size())
        fout << "Ciclu negativ!";
    else
        for (auto i = 2u; i < bestWay.size(); i++)
            fout << bestWay[i] << " ";
    fout << '\n';

    return 0;
}