#include <bits/stdc++.h>

using namespace std;

// ifstream in("IO/citire.in");

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int infinity = numeric_limits<int>::max();
// Muchie de la x la y cu costul cost
struct Muchie
{
    int x, y;
    int cost = 0;

    Muchie() = default;

    Muchie(int x, int y, int cost)
    {
        this->x = x;
        this->y = y;
        this->cost = cost;
    }
};

struct Nod
{
    int nod;
    int cost = 0;
    // nodul x are in lista de adiacenta un Nod cu nod=y si costul = 10 daca avem muchie de la x la y cu costul 10

    Nod() = default;
    Nod(int nod) { this->nod = nod; }
    Nod(int nod, int cost)
    {
        this->nod = nod;
        this->cost = cost;
    }
};

class Graf
{
public:
    int nrNoduri;
    int nrMuchii;
    vector<bool> vizitat;
    vector<int> grad_intern;
    vector<int> grad_extern;
    vector<vector<Nod>> lista_adiacenta;
    vector<Muchie> muchii;

    Graf() = default;

    Graf(int nrNoduri)
    {
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }
    Graf(int nrNoduri, int nrMuchii)
    {
        this->nrMuchii = nrMuchii;
        this->nrNoduri = nrNoduri;
        vizitat.resize(nrNoduri + 1);
        grad_intern.resize(nrNoduri + 1, 0);
        grad_extern.resize(nrNoduri + 1, 0);
        lista_adiacenta.resize(nrNoduri + 1);
    }

    void calculeazaGrad()
    {
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            for (auto vecin : lista_adiacenta[nod])
            {
                grad_intern[vecin.nod] += 1;
                grad_extern[nod] += 1;
            }
        }
    }

    void dfs(int start, stack<int> &stiva)
    {
        vizitat[start] = true;
        for (auto vecin : lista_adiacenta[start])
        {
            if (vizitat[vecin.nod] == false)
            {
                dfs(vecin.nod, stiva);
            }
        }
        stiva.push(start);
    }

    vector<int> sortareTopologica()
    {
        vector<int> noduri_start;
        stack<int> stiva;
        for (int nod = 1; nod <= nrNoduri; nod++)
        {
            if (grad_intern[nod] == 0)
            {
                noduri_start.push_back(nod);
            }
        }

        for (auto nod : noduri_start)
        {
            dfs(nod, stiva);
        }

        vector<int> sortaretopologica;
        while (!stiva.empty())
        {
            sortaretopologica.push_back(stiva.top());
            stiva.pop();
        }

        return sortaretopologica;
    }

    void printGraf()
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << ": ";
            for (auto nod : lista_adiacenta[i])
                cout << nod.nod << "(" << nod.cost << ") ";
            cout << endl;
        }
    }

    void printGrad()
    {
        for (int i = 1; i <= nrNoduri; i++)
        {
            cout << i << "-> grad intern = " << grad_intern[i] << ", grad extern = " << grad_extern[i] << endl;
        }
    }

    // drumul de cost maxim pentru graf orientat/neorientat aciclic de sursa si final unic
    // costul maxim  = drum[end]
    // drumul se obtine de la end pana ajungem la sursa prin vectorul de tati
    void drumCritic(int sursa, vector<int> &drum, vector<int> &tata)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = -1;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        vector<int> top = sortareTopologica();
        for (auto nod : top)
        {
            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] + vecin.cost > drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    void Djikstra(int sursa, vector<int> &drum, vector<int> &tata)
    {
        drum.clear();
        tata.clear();
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;

        auto cmp = [&](int nod1, int nod2)
        { return drum[nod1] > drum[nod2]; };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

        // daca am adaugat o sursa imaginara si doresc sa pornesc din locuri multiple :
        // for (int i = 1; i <= nrNoduri; i++)
        //     pq.push(i);

        pq.push(sursa);
        while (!pq.empty())
        {
            int nod = pq.top();
            pq.pop();

            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] + vecin.cost < drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    pq.push(vecin.nod);
                    tata[vecin.nod] = nod;
                }
            }
        }
    }

    // intoarce false daca contine circuit negativ, true daca nu
    bool BellmanFord(int sursa, vector<int> &drum, vector<int> &tata, int &negativStart)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        for (int k = 1; k <= nrNoduri - 1; k++)
        {
            for (auto muchie : muchii)
            {
                if (drum[muchie.x] < infinity && drum[muchie.x] + muchie.cost < drum[muchie.y])
                {
                    drum[muchie.y] = drum[muchie.x] + muchie.cost;
                    tata[muchie.y] = muchie.x;
                }
            }
        }
        // a n a rulare a algoritmului pentru a detecta ciclul negativ
        for (auto muchie : muchii)
        {
            if (drum[muchie.x] < infinity && drum[muchie.x] + muchie.cost < drum[muchie.y])
            {
                drum[muchie.y] = drum[muchie.x] + muchie.cost;
                tata[muchie.y] = muchie.x;
                negativStart = muchie.y;
                return false;
            }
        }
        return true;
    }

    bool BellmanFordQueue(int sursa, vector<int> &drum, vector<int> &tata, int &negativStart)
    {
        drum.resize(nrNoduri + 1);
        tata.resize(nrNoduri + 1);
        for (int i = 1; i <= nrNoduri; i++)
        {
            drum[i] = infinity;
            tata[i] = 0;
        }
        drum[sursa] = 0;
        vector<bool> inQueue(nrNoduri + 1, false);
        queue<int> q;
        q.push(sursa);
        inQueue[sursa] = true;
        vector<int> lungime(nrNoduri + 1, 0);
        while (!q.empty())
        {
            int nod = q.front();
            q.pop();
            inQueue[nod] = false;
            for (auto vecin : lista_adiacenta[nod])
            {
                if (drum[nod] < infinity && drum[nod] + vecin.cost < drum[vecin.nod])
                {
                    drum[vecin.nod] = drum[nod] + vecin.cost;
                    tata[vecin.nod] = nod;
                    if (inQueue[vecin.nod] == false)
                    {
                        q.push(vecin.nod);
                        inQueue[vecin.nod] = true;
                    }
                    lungime[vecin.nod] = lungime[nod] + 1;
                    if (lungime[vecin.nod] > nrNoduri - 1)
                    {
                        negativStart = vecin.nod;
                        return false;
                    }
                }
            }
        }
        return true;
    }

    void afisareDrum(int start, int end, vector<int> tata)
    {
        // cout << start << " " << end << endl;
        // for (int i = 1; i <= nrNoduri; i++)
        //     cout << tata[i] << " ";
        // cout << endl;
        vector<int> drum;
        if (start != end) // daca e circuit nu trebuie sa punem finalul de 2 ori
            drum.push_back(end);
        while (tata[end] != start)
        {
            end = tata[end];
            drum.push_back(end);
        }
        drum.push_back(start);
        for (int i = drum.size() - 1; i >= 0; i--)
            cout << drum[i] << " ";
    }
};

int main()
{
    int n, m;
    in >> n >> m;
    Graf graf(n, m);
    for (int i = 1; i <= graf.nrMuchii; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        graf.muchii.push_back(Muchie(x, y, c));
        graf.lista_adiacenta[x].push_back(Nod(y, c));
    }
    int start = 1;
    // in >> start;
    // graf.calculeazaGrad();
    // graf.printGraf();
    // graf.printGrad();
    vector<int> drum;
    vector<int> tata;
    int negativ;
    if (graf.BellmanFord(start, drum, tata, negativ) == true)
    {
        // for (int i = 1; i <= graf.nrNoduri; i++)
        // {
        //     if (i != start)
        //     {
        //         cout << "Drum: ";
        //         graf.afisareDrum(start, i, tata);
        //         cout << "Cost: " << drum[i] << endl;
        //     }
        // }
        for (int i = 2; i <= graf.nrNoduri; i++)
        {
            out << drum[i] << " ";
        }
    }
    else
    {
        out << "Ciclu negativ!";
        // cout << "Circuit de cost negativ: \n";
        // vector<int> circuit;
        // graf.afisareDrum(negativ, negativ, tata);
    }

    return 0;
}