#define fisier "bellmanford"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
#include <utility>
#include <vector>
using ListaVecini = std::vector<std::pair<int, int>>;
const int N = 50000, M = 250000, C = 1000, INF = C*M;
#include <deque>
std::pair<bool, std::vector<int>> bellmanFord(ListaVecini* vecini, int rad, int n)
{
    std::vector<int> dist(n, INF), relax(n, 0);
    dist[rad] = 0;
    for (std::deque<int> deq = {rad}; deq.size(); deq.pop_front())
    {
        for (auto arc: vecini[deq.front()])
        {
            int nouDist = dist[deq.front()] + arc.first;
            if (nouDist < dist[arc.second])
            {
                dist[arc.second] = nouDist;
                deq.push_back(arc.second);
                if (++relax[arc.second] == n)
                    return {false, {}};
            }
        }
    }
    dist.erase(dist.begin());
    return {true, dist};
}
int main()
{
    static ListaVecini vecini[N];
    int n, m;
    in >> n >> m;
    while (m--)
    {
        int a, b, c;
        in >> a >> b >> c;
        vecini[--a].push_back({c, --b});
    }
    auto raspuns = bellmanFord(vecini, 0, n);
    if (raspuns.first)
        for (int nod: raspuns.second)
            out << nod << ' ';
    else
        out << "Ciclu negativ!";
}