// O(n*m) worst case care in practica are de fapt performante asemanatoare cu Dijkstra pt determinarea drumului de cost minim
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define Nmax 50001
using namespace std;

ifstream fin("bellmanford.in"); // putem avea costuri negative => nu merge dijkstra, ci fol bellman-ford
ofstream fout("bellmanford.out"); // bellman-ford detectează existența de circuite negative

// lanţ de la nodul 1 la toate celelalte
int n,m;
vector<pair<int,int>> LA[Nmax]; // lista de adiacenta: LA.first = nodul x ; LA.second = costul de la sursa pana la x;
vector<int> D(Nmax, 1 << 30);   // matricea distantelor minime, initializata cu infinit
vector<int> cnt(Nmax);  // vector de frecventa = contorul vecinilor unui nod

vector<int> BellmanFord(int startNod) // nu e functie recursiva
{
    D[startNod] = 0; // D pt nodul de start = de la el tot la el => 0
    int are_ciclu = 0;

    // BFS
    // Se va încerca îmbunătăţirea costului nodurilor vecine, introducându-le în listă în cazul scăderii costului, dacă nu apar deja
    queue<int> q;   // coadă cu vârfurile ale căror etichetă s-a actualizat
    vector<bool> viz(Nmax);
    q.push(startNod); // pun nodul 1 de start in coada

    while(!q.empty() && !are_ciclu) {  // cat mai am muchii de procesat
        int nodCurent = q.front(); // primul din coada
        q.pop();
        viz[nodCurent] = false; // ca si cum nu e in coada

        for (auto vecin : LA[nodCurent]) // merg pe fiii sai
        {
            if (D[vecin.first] > D[nodCurent] + vecin.second) // d[v] > d[u] + w(u,v) adica am gasit un drum mai scurt
            {
                if (!viz[vecin.first]) // daca nu am bagat deja in coada acelasi nod <=> optimizare finala
                {
                    q.push(vecin.first);
                    cnt[vecin.first]++;  // numar de cate ori am trecut prin vecinii vecinului nodului curent
                    viz[vecin.first] = true; // abia acum putem spune ca a fost bagat in coada

                    if (cnt[vecin.first] > n)  // daca a trecut de mai mult de n ori prin acelasi nod, inseamna ca e un ciclu
                    {                       // pt ca e nev de maxim n-1 iteratii pt a gasi dist min (adica pt a trece prin toate celalte noduri)
                        are_ciclu = 1;  // AVEM CICLU;
                        // fout << "Ciclu negativ!";
                    }
                }
                D[vecin.first] = D[nodCurent] + vecin.second; // relaxarea muchiei  = actualiz drum mai scurt
            }
        }
    }
    if (are_ciclu)
        D[startNod] = -1; // ca sa pot afisa -1 pt ciclu negativ
    return D;
}


int main()
{
    int x,y,c;
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        LA[x].emplace_back(y, c);
    }

    cout << "plec din 1\n";
    D = BellmanFord(1);

    if(D[1] == -1){
        fout << "Ciclu negativ!";
        return 0;
    }

    for (int i=2; i<=n; i++) // Al i-lea număr va reprezenta costul minim al unui lanţ de la nodul 1 la nodul i+1.
        fout << D[i] << " ";

    return 0;
}