#include <fstream>
#include <vector>

using namespace std;
const int NMAX = 50001, //MMAX = 250001,
          INF = 1 << 29;

struct muchie
{
    int x, y, w;
};

int N, M,
    D[NMAX]; ///D[i] = distanta minima de la nodul src la i

vector<muchie> G;


ifstream f("bellmanford.in");
//ifstream f(".\\Teste\\grader_test2.in");
ofstream g("bellmanford.out");

void citire()
{
    int x, y, w;
    f >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        f >> x >> y >> w;
        G.push_back({x, y, w});
    }
}

void init(int s)
{
    for(int i = 1; i <= N; i++)
        D[i] = INF;
    D[s] = 0;
}

bool BellmanFord(int s) ///Varianta 1
{
    init(s);
    for(int i = 1; i < N; i++)
        for(muchie &m : G)
        {
            if(D[m.x] < INF)
                D[m.y] = min(D[m.y], D[m.x] + m.w);
        }
    //
    for(muchie &m : G)            ///Se verifică dacă se poate îmbunătăți vreo distanță
    {
        if(D[m.x] + m.w < D[m.y]) ///==> Graful are un ciclu de cost negativ
            return 0;
    }
    return 1;
}

int main()
{
    citire();
    if(BellmanFord(1))
    {
        for(int i = 2; i <= N; i++)
            g << D[i] << ' ';
    }
    else
        g << "Ciclu negativ!";
    f.close();
    g.close();
    return 0;
}
/**
   Algoritmul Bellman-Ford
   =======================
   Determină drumurile de cost minim dintre un nod desemnat ca sursă (plecare)
   şi restul nodurilor accesibile lui chiar dacă există costuri negative pe arce.

   Aceste rezultate sunt furnizate numai în situaţia în care nodul de plecare
   nu face parte dintr-un circuit/ciclu de cost negativ.

   Cicluri (circuite) cu cost negativ
   ==================================
   Dacă există cicluri cu cost negativ, atunci căutarea unui drum minim NU are sens,
   deoarece se poate ajunge de la un nod la acelaşi nod, folosind acelaşi ciclu de oricâte ori
     ==> costul minim = -infinit.

   Algoritmul folosește același mecanism de relaxare ca si Dijkstra, dar, spre
   deosebire de acesta, nu optimizează o soluție folosind un criteriu de optim local,
   ci parcurge fiecare muchie de un număr de ori egal cu numărul de noduri si
   încearcă sa o relaxeze de fiecare dată, pentru a îmbunătăți distanta până
   la nodul destinație al muchiei curente.

   Relaxarea unei muchii (arc)
   ===========================
   Relaxarea unei muchii (u, v) constă în a testa dacă se poate reduce
   distanța/costul drumului de la sursa s până la nodul v, trecând prin nodul
   intermediar u și apoi circulând pe muchia (u, v).
   Fie
       ● w(u,v) costul inițial al muchiei (u, v),
       ● d[u] costul drumului de la sursa s la u și
       ● d[v] costul drumului de la sursa s la v.
   Dacă d[v] > d[u] + w(u,v), atunci muchia (u, v) este relaxată și
   drumul anterior s ─►∙∙∙─► v (care nu trece prin u) este înlocuit cu
   drumul s ─►∙∙∙─► u ─► v (care trece prin u și care are cost mai mic).


   Drumul minim dintre sursă și orice nod destinație poate să treacă prin maximum
   |V| noduri (adică toate nodurile grafului), respectiv |V|-1 muchii.
   Prin urmare, relaxarea tuturor muchiilor de |V|-1 ori este suficientă pentru
   a propaga până la toate nodurile informația despre distanta minimă de la sursă.

   Dacă, la sfârșitul acestor |E|*(|V|-1) relaxări, mai poate fi îmbunătățită o distanță,
   atunci graful are un ciclu de cost negativ și problema nu are soluție.

  BellmanFord(G,s) // G = (V,E), s = sursa
  ========================================
  ● Pentru fiecare v din V                   //inițializări
    │ d[v] = ∞ (infinit)
    │ T[v] = 0                               //Tatăl (părintele) lui v
    └■
  ● d[s] = 0                                 //actualizare distanță de la s la s
  ● Pentru i de la 1 la |V|-1                //pentru fiecare pas de la s spre V\{s}
    │  Pentru fiecare (u,v) din E            //pentru arcele ce pleacă de la nodurile deja considerate
    │  │    Dacă d[v] > d[u] + w(u,v) atunci //se relaxează arcele corespunzătoare
    │  │     │ d[v] = d[u] + w(u,v);
    │  │     │ T[v] = u;
    │  │     └■
    │  └■
    └■
  ● Pentru fiecare (u,v) din E
    │ Dacă d[v] > d[u] + w(u,v) atunci
    │   │ Eroare ("ciclu negativ");
    │   └■
    └■

   Complexitate algoritm: O(|E|*|V|).


   Poate fi folosit si pentru grafuri ce conțin muchii de cost negativ,
   dar nu poate fi folosit pentru grafuri ce conțin cicluri de cost negativ
   (când căutarea unui drum minim nu are sens).
   Cu ajutorul său putem afla daca un graf conține cicluri.

*/