#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <climits>

#define INFINIT INT_MAX

using namespace std;

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

class Graf {
private:
    int nrNoduri;
    bool eOrientat, arePonderi;
    vector<int> *adiacenta; // lista de vecini

    vector<pair<int, pair<int, int>>> muchii;
public:
    explicit Graf(int nrNoduri);

    Graf(int nrNoduri, const bool eOrientat, const bool arePonderi);

    void citire(const int nrMuchii);

    void rezolvaBellmanFord(int &nrMuchii);

    ~Graf();

private:
    void adaugaMuchie(const int sursa, const int destinatie);

    void adaugaMuchiePonderat(const int sursa, const int destinatie, const int cost);

};



void Graf::rezolvaBellmanFord(int &nrMuchii) {
    vector<vector<pair<int, int>>> adiacentaCost(nrNoduri + 1, vector<pair<int, int>>(1, {-1, -1}));
    for (int i = 1; i <= nrMuchii; i++) {
        adiacentaCost[muchii[i].second.first].push_back(make_pair(muchii[i].second.second, muchii[i].first));
    }
    vector<int> distanta(nrNoduri + 1, INFINIT);
    vector<int> vizitat(nrNoduri + 1, 0);
    vector<int> apartCoada(nrNoduri + 1, 0); // verfica daca un nod se gaseste in coada
    // de ce? pentru ca nu vreau sa il pun de mai multe ori in coada
    // daca l-as pune de mai multe ori in coada, ar verifica pentru aceasi imbunatatire de mai multe ori (acelasi drum)
    // daca verific de mai multe ori acelasi drum, se incrementeaza counter-ul de mai multe ori la acelasi pas,
    // ceea ce imi va strica verificarea de ciclu negativ
    bool cicluNegativ = false;
    queue<int> coada2;
    coada2.push(1); // introduc in coada nodulStart
    apartCoada[1] = 1; //
    distanta[1] = 0; // distanta pana la nodulStart este 0

    while (!coada2.empty() && !cicluNegativ) {
        int nod = coada2.front();
        coada2.pop();
        apartCoada[nod] = 0;

        for (int i = 1; i < adiacentaCost[nod].size(); i++)
            if (distanta[nod] + adiacentaCost[nod][i].second < distanta[adiacentaCost[nod][i].first]) {
                distanta[adiacentaCost[nod][i].first] = distanta[nod] + adiacentaCost[nod][i].second;
                vizitat[adiacentaCost[nod][i].first]++;

                if (vizitat[adiacentaCost[nod][i].first] >= nrNoduri) {
                    // daca am vizitat un nod adiacent cu mine de mai multe ori decat numarul de noduri
                    // inseamna ca avem un ciclu negativ
                    cicluNegativ = true;
                    break;
                }

                if (!apartCoada[adiacentaCost[nod][i].first]) {
                    coada2.push(adiacentaCost[nod][i].first);
                    apartCoada[adiacentaCost[nod][i].first] = 1;
                }
            }
    }
    if (cicluNegativ) {
        fout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= nrNoduri; i++)
            fout << distanta[i] << " ";
    }

}

int main() {
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;
    Graf g1(nrNoduri, true, true);
    g1.citire(nrMuchii);
    g1.rezolvaBellmanFord(nrMuchii);

    fin.close();
    fout.close();
    return 0;
}

Graf::Graf(const int nrNoduri) {
    this->nrNoduri = nrNoduri;
}

Graf::Graf(const int nrNoduri, const bool eOrientat, const bool arePonderi) {
    this->nrNoduri = nrNoduri;
    this->eOrientat = eOrientat;
    this->arePonderi = arePonderi;
}

void Graf::adaugaMuchie(const int sursa, const int destinatie) {
    adiacenta[sursa].push_back(destinatie);
}

void Graf::adaugaMuchiePonderat(const int sursa, const int destinatie, const int cost) {
//    adiacentaCost[sursa].push_back(muchieCost(destinatie, cost));
}

void Graf::citire(const int nrMuchii) {
    int sursa, destinatie; // extremitate muchie stanga respectiv dreapta
    adiacenta = new vector<int>[nrNoduri + 1];
    if (!arePonderi) {
        if (eOrientat)
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie;
                adaugaMuchie(sursa, destinatie);
            }
        else
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie;
                adaugaMuchie(sursa, destinatie);
                adaugaMuchie(destinatie, sursa);
            }
    } else {
        int cost; // costul muchiei
        muchii.resize(nrMuchii + 1);
        if (eOrientat)
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie >> cost;
                muchii[i] = {cost, {sursa, destinatie}};
            }
        else
            for (int i = 1; i <= nrMuchii; i++) {
                fin >> sursa >> destinatie >> cost;
                muchii[i] = {cost, {sursa, destinatie}};
            }
    }
}

Graf::~Graf() {
    delete[] adiacenta;
}