#include <bits/stdc++.h>

#define NMax 101
#define inf 2e9
#define NMax5 50005

using namespace std;

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


class graf
{
    int nrNoduri, nrMuchii;
    bool orientat;
    vector <int> gr[NMax]; // liste de adiacenta ale grafului
    pair< int, pair<int, int> > v[NMax]; // structura de date pt APM


public:
    graf(int n, int m, bool o); // constructor
    void Citire_Orientat();
    void Citire_Neorientat();
    void Citire_Neorientat_Ponderat();
    void Afisare_Graf();

    void BFS(int s); // s - nodul de start
    void DFS(int s); // s - nodul de start

    // Determinare nr de componente conexe
    void Comp_Conexe(); // afiseaza cate componente conexe are graful

    // Kosaraju
    void Graf_Transpus(); // creeaza graful transpus in grT
    void ParcurgereGrafInitial(); // parcurgerea in adancime a grafului initial
    void DFST(int s, int culoare); // s - nodul de start, dfs pe graful transpus
    void CTC(); // apeleasa DFST si afiseaza comp tare conexe

    // Sortare topologica
    void Sortare_Topologica();

    // Algoritm Havel-Hakimi
    bool Havel_Hakimi(vector<int>grade, int nrNoduri);

    // Afisare Muchii Critice
    void Muchii_Critice();
    void DFS_Critice(int s, int tata);

    // Afisare Componente Biconexe
    void DFS_Biconex(int s, int tata);
    void Componente_Biconexe();

    // APM
    void Kruskal();

    // Dijkstra
    void Dijkstra(int s);

    // Bellman-Ford
    void Bellman_Ford(int s);
};




// DFS, BFS, Muchii critice, Componente biconexe
bool viz[NMax];

// Kosaraju
stack <int> S; // stiva pentru memorarea nodurilor in ordinea timpilor de final
bool vizDFST[NMax]; // pt graful transpus
vector <int> grT[NMax]; // liste de adiacenta ale grafului transpus
vector <int> componente[NMax]; // liste cu nodurile care compun fiecare componenta tare conexa in parte

// Havel-Hakimi
vector <int> grade;

// Muchii Critice + Componente Biconexe
int nivel[NMax]; // nivelul pe care se gaseste nodul
int niv_min_acc[NMax]; // nivelul minim accesibil
int ct_muchii_critice;
vector <vector<int>> muchii_critice;

// Componente Biconexe
int ct_biconexe;
stack <int> S2;
vector <int> componente_biconexe[NMax];


// Kruskal


// Dijkstra
priority_queue <pair<int,int>> q;   // coada cu prioritati {cost,nod}
vector <pair<int,int>> muchii[NMax5];
bool vizDij[NMax5];     // viz[x] = 1 daca nodul a fost vizitat
int dist[NMax5];     // dist[x] = distanta de la nodul de start la nodul x

// Bellman-Ford




graf :: graf(int n, int m, bool o)
{
    nrNoduri = n;
    nrMuchii = m;
    orientat = o;
}

void graf :: Citire_Orientat()
{
    for(int i = 1; i <= nrMuchii; ++i)
    {
        int x, y;
        fin >> x >> y;
        gr[x].push_back(y);
    }
}

void graf :: Citire_Neorientat()
{
    for(int i = 1; i <= nrMuchii; ++i)
    {
        int x, y;
        fin >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
}

void graf :: Citire_Neorientat_Ponderat()
{
    for(int i = 1; i <= nrMuchii; ++i)
    {
        fin >> v[i].second.first >> v[i].second.second; // muchia (x,y)
        fin >> v[i].first;                              // cu costul c
    }
}

void graf :: Graf_Transpus()
{
    for(int i = 1; i <= nrNoduri; ++i)
        for(auto j : gr[i])
            grT[j].push_back(i);
}

void graf :: Afisare_Graf()
{
    for(int i=1; i <= nrNoduri; ++i)
    {
        fout << i << " : " ;
        for(auto j: gr[i])
            fout << j << " ";
        fout << "\n";
    }
}

void graf :: BFS(int s)
{
    int distanta[NMax] = {0};
    queue <int> q;

    viz[s] = 1;
    q.push(s);

    while(!q.empty())
    {
        int k = q.front();  // elem din varful cozii
        q.pop();            // sterg elem din varful cozii
        for(auto i : gr[k])
            if(!viz[i])
            {
                viz[i] = 1;
                q.push(i);
                distanta[i] = distanta[k] + 1;
            }
    }

    for(int i = 1; i <= nrNoduri; ++i)
        if(viz[i])
            fout << distanta[i] << " ";
        else
            fout << -1 << " ";
}

void graf :: DFS(int s)
{
    viz[s] = 1;
    for(auto i : gr[s])
        if(!viz[i])
            DFS(i);

    // pentru CTC(Kosaraju) - stabilim timpul de finalizare pentru nodul s
    S.push(s);
}

void graf :: Comp_Conexe()
{
    int ct = 0;
    for(int i = 1; i <= nrNoduri; ++i)
        if(!viz[i])
        {
            ct++;
            DFS(i);
        }
    fout << ct;
}

void graf :: ParcurgereGrafInitial()
{
    for(int i = 1; i <= nrNoduri; ++i)
        if(!viz[i])
            DFS(i);
}

void graf :: DFST(int s, int ct)
{
    vizDFST[s] = 1;
    componente[ct].push_back(s);

    for(auto i : grT[s])
        if(!vizDFST[i])
            DFST(i, ct);
}

void graf :: CTC()
{
    int ct_ctc = 0;

    while(!S.empty())
    {
        int varf = S.top();
        S.pop();
        if(!vizDFST[varf])
        {
            ct_ctc ++;
            DFST(varf, ct_ctc);
        }
    }

    fout << ct_ctc << "\n";

    for(int i = 1; i <= ct_ctc; ++i)
    {
        for(auto j:componente[i])
            fout << j << " ";
        fout << "\n";
    }
}

void graf :: Sortare_Topologica() // o parcurgere in adancime a grafului unde se determina timpii de finalizare pt fiecare nod
{
    // nodurile vor fi afisate in ordinea descrescatoare a timpilor de finalizare
    ParcurgereGrafInitial();

    while(!S.empty())
    {
        fout << S.top() << " ";
        S.pop();
    }
}

bool myfunction(int i, int j)
{
    return (i>j);
}

bool graf :: Havel_Hakimi(vector <int> grade, int nrNoduri)
{
    bool ok =1;

    while(ok)
    {
        sort(grade.begin(), grade.end(), myfunction);

        if(grade[0] == 0) // daca cel mai mare element dupa sortare este 0 => toate elementele sunt 0 => se poate forma
            return true;

        if(grade[0] > grade.size() - 1) // daca gradul este mai mare decat nr de noduri curente - 1 => NU se poate forma
            return false;

        int grad_curent = grade[0];
        grade.erase(grade.begin() + 0); // elimin primul element

        for(int i = 0; i < grad_curent; ++i) // scad 1 doar din primele grad_curent elemente
        {
            grade[i] --;
            if(grade[i] < 0)
                return false;
        }
    }
}

void graf :: DFS_Critice(int s, int tata)
{
    viz[s] = 1;
    nivel[s] = nivel[tata] + 1; // calculam nivelul pe care se afla nodul curent s
    niv_min_acc[s] = nivel[s]; // nivelul minim accesibil este acelasi cu nivelul pe care se afla nodul curent s pentru moment

    for(auto i : gr[s])
        if(i != tata)
        {
            if(viz[i] == 1)   // (s,i) ar fi muchie de intoarcere (deci nu poate fi muchie critica) deoarece i a fost vizitat deja
            {
                if(niv_min_acc[s] > nivel[i])
                    niv_min_acc[s] = nivel[i];
            }
            else
            {
                DFS_Critice(i,s);
                if(niv_min_acc[s] > niv_min_acc[i])
                    niv_min_acc[s] = niv_min_acc[i];
            }

            // determinare muchii critice
            if(nivel[s] < niv_min_acc[i]) // conditie necesara ca (s,i) sa fie muchie critica
            {
                // (s, i)
                ct_muchii_critice++;
                vector <int> v1;
                v1.push_back(s);
                v1.push_back(i);
                muchii_critice.push_back(v1);
            }
        }
}

void graf :: Muchii_Critice()
{
    DFS_Critice(1,0);

    fout << ct_muchii_critice << "\n";

    for( vector<vector<int>>::iterator i = muchii_critice.begin() ; i != muchii_critice.end(); i++ )
    {
        fout << "[" ;
        vector<int>::iterator j = i->begin();
        fout<<*j;
        fout << ",";
        j++;
        fout <<*j;
        fout << "] ";
    }
}


void graf :: DFS_Biconex(int s, int tata)
{
    viz[s] = 1;
    S2.push(s); // adaugam nodurile in stiva S2 in oridinea in care le vizitam

    nivel[s] = nivel[tata] + 1; // calculam nivelul pe care se afla nodul curent s
    niv_min_acc[s] = nivel[s];  // nivelul minim accesibil este acelasi cu nivelul pe care se afla nodul curent s pentru moment

    for (auto i : gr[s])
    {
        if (viz[i] == 1)       // (s,i) ar fi muchie de intoarcere (deci nu poate fi muchie critica) deoarece i a fost vizitat deja
        {
            if(niv_min_acc[s] > nivel[i])
                niv_min_acc[s] = nivel[i];
        }
        else
        {
            DFS_Biconex(i, s);

            if(niv_min_acc[s] > niv_min_acc[i])
                niv_min_acc[s] = niv_min_acc[i];


            // determinare componente biconexe
            if(niv_min_acc[i] >= nivel[s])
            {
                ct_biconexe ++;

                while(!S2.empty() && S2.top() != i) // eliminam nodurile pana la nodul i
                {
                    componente_biconexe[ct_biconexe].push_back(S2.top());
                    S2.pop();
                }
                componente_biconexe[ct_biconexe].push_back(S2.top()); // adaugam si nodul i
                S2.pop();
                componente_biconexe[ct_biconexe].push_back(s);        // adaugam si nodul s
            }
        }
    }
}

void graf :: Componente_Biconexe()
{
    DFS_Biconex(1,0);

    fout << ct_biconexe << "\n";

    for(int i = 1; i <= ct_biconexe; ++i)
    {
        for(auto j : componente_biconexe[i])
            fout << j << " ";
        fout << "\n";
    }
}


void graf :: Kruskal()
{
    sort(v + 1, v + nrMuchii + 1); // sortam crescator muchiile in functie de cost

    int C[NMax];       // C[x] = numarul componentei conexe din care face parte nodul x
    int cost = 0, ct_muchii_adaugate = 0;
    int Sol[NMax];

    for(int i = 1; i <= nrNoduri; ++i) C[i] = i;        // initial se pleaca cu n arbori formati dintr-un singur nod

    for(int i = 1; i <= nrMuchii && ct_muchii_adaugate < nrNoduri - 1; ++i)
    {
        // verificam daca muchia i poate fi adaugata
        // cele doua extremitati trebuie sa faca parte din compomnente conexe diferite
        if(C[v[i].second.first] != C[v[i].second.second])
        {
            cost += v[i].first;      // marim costul arborelui

            ct_muchii_adaugate++;    // adaugam muchia de ordin i la arbore
            Sol[ct_muchii_adaugate] = i;

            // unificare
            int cx = C[v[i].second.first];
            int cy = C[v[i].second.second];
            for(int j = 1; j <= nrNoduri; ++j)
                if(C[j] == cx)
                    C[j] = cy;
        }
    }

    // afisare cost, nr muchii si muchii
    fout << cost << "\n" << ct_muchii_adaugate << "\n";
    for(int i = 1; i <= ct_muchii_adaugate; ++i)
        fout<<v[ Sol[i] ].second.first << " " << v[ Sol[i] ].second.second << "\n";

}

void graf :: Dijkstra(int s)
{
    q.push({0,s});  // adaugam in coada nodul de inceput cu costul 0 (de la s la s avem distanta 0)
    vizDij[s] = 1;     // marcam nodul ca fiind vizitat
    dist[s] = 0;    // distanta de la s la s va fi 0

    while(!q.empty())
    {
        int nod_curent = q.top().second;    // nodul curent
        // int cost = q.top().first; // costul
        q.pop();

        vizDij[nod_curent] = 0; // presupunem ca nodul curent nu a fost vizitat inca

        for(auto i : muchii[nod_curent])  // parcurgem nodurile adiacente cu nodul curent
        {
            int y = i.second;      // nodul adiacent cu nodul curent
            int cost = i.first;    // costul de la nodul curent  pana la y

            if(dist[nod_curent] + cost < dist[y])
            {
                dist[y] = dist[nod_curent] + cost;
                if(!vizDij[y]) // marcam nodul ca fiind vizitat daca nu era
                {
                    vizDij[y] = 1;
                    q.push({dist[y],y});
                }
            }
        }
    }

    // afisare
    for(int i = 2; i <= nrNoduri; ++i)
    {
        if(dist[i] != inf)
            fout << dist[i] << " ";
        else
            fout << 0 << " ";
    }
}

void graf :: Bellman_Ford(int s)
{
    queue <int> C;
    vector <bool> adaugat(nrNoduri + 1, 0);
    vector <int> dist(nrNoduri + 1, inf);
    vector <int> viz(nrNoduri + 1, 0);
    bool ciclu_negativ = 0;

    // declarare si citire graf ponderat
    vector <vector <pair<int, int> >> muchii(nrNoduri + 1);
    for(int i = 1; i <= nrMuchii; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        muchii[x].push_back({cost,y});
    }

    C.push(s);          // adaugam nodul s in coada
    dist[s] = 0;        // distanta de la s la s va fi 0
    adaugat[s] = 1;     // marcam cu 1 nodul ca fiind adaugat in coada

    while(!C.empty() && !ciclu_negativ)
    {
        int nod_curent = C.front();
        C.pop();
        adaugat[nod_curent] = 0; // punem 0 pt ca nodul a fost eliminat din coada


        for(int i = 0; i < muchii[nod_curent].size(); ++i) // parcurgem nodurile adiacente cu nodul curent
        {
            int y = muchii[nod_curent][i].second;   // nodul destinatie
            int cost = muchii[nod_curent][i].first; // costul de la nodul curent la nodul destinatie

            if(dist[nod_curent] + cost < dist[y])   // recalculam distanta minima daca este necesar
            {
                dist[y] = dist[nod_curent] + cost;

                if(!adaugat[y]) // adaugam nodul in coada daca nu exista deja
                {
                    C.push(y);
                    adaugat[y] = 1;
                }

                viz[y] ++;
                if(viz[y] >= nrNoduri) // cazul pt care se formeaza ciclu negativ
                {
                    ciclu_negativ = 1;
                    break;
                }
            }
        }
    }

    // afisare distante/ciclu negativ
    if(!ciclu_negativ)
    {
        for(int i = 2; i <= nrNoduri; ++i)
            fout << dist[i] << " ";
    }
    else
        fout << "Ciclu negativ!";
}


int N, M;

int main()
{

    fin >> N >> M;
    graf G(N, M, 0);
    G.Bellman_Ford(1);

    /*
    cout << "Alegeti task-ul:\n Task 1: DFS - Afisare numar componente conexe\n Task 2: BFS\n Task 3: Determinare CTC\n Task 4: Havel-Hakimi\n";
    cout << " Task 5: Sortare topologica\n Task 6: Afisare muchii critice\n Task 7: Componente biconexe\n Task 8: APM\n Task 9: Dijkstra\n Task 10: Bellman-Ford\n Task 11: Disjoint\n\n";
    cout << "Scrie task-ul : ";

    int task;
    cin >> task;

    if(task == 1) // DFS - nr comp conexe
    {
        int s;
        fin >> N >> M;
        graf G(N, M, 0);
        G.Citire_Neorientat();
        G.Comp_Conexe();
    }
    else if(task == 2) // BFS
    {
        int s;
        fin >> N >> M >> s;
        graf G(N, M, 1);
        G.Citire_Orientat();
        G.BFS(s);
    }
    else if(task == 3) // Componente tare conexe
    {
        fin >> N >> M;
        graf G(N, M, 1);
        G.Citire_Orientat();
        G.Graf_Transpus();
        G.ParcurgereGrafInitial();
        G.CTC();
    }
    else if(task == 4) // Havel - Hakimi
    {
        fin >> N;
        graf G(N, 0, 0);
        for(int i = 1; i <= N; ++i)
        {
            int x;
            fin >> x;
            grade.push_back(x);
        }
        if(G.Havel_Hakimi(grade, N))
            fout << "DA se poate construi un graf.";
        else fout << "NU se poate construi un graf. ";
    }
    else if(task == 5) // Sortare Topologica
    {
        fin >> N >> M;
        graf G(N, M, 1);
        G.Citire_Orientat();
        G.Sortare_Topologica();
    }
    else if(task == 6) // Muchii critice
    {
        fin >> N >> M;
        graf G(N, M, 0);
        G.Citire_Neorientat();
        G.Muchii_Critice();
    }
    else if(task == 7) // Componente biconexe
    {
        fin >> N >> M;
        graf G(N, M, 0);
        G.Citire_Neorientat();
        G.Componente_Biconexe();
    }
    else if(task == 8) // APM
    {
        fin >> N >> M;
        graf G(N, M, 0);
        G.Citire_Neorientat_Ponderat();
        G.Kruskal();
    }
    else if(task == 9) // Dijkstra
    {
        fin >> N >> M;
        graf G(N, M, 0);

        //citire
        for(int i = 1; i <= M; ++i)
        {
            int x, y, cost;
            fin >> x >> y >> cost;
            muchii[x].push_back({cost,y});
        }

        // initial presupunem fiecare distanta ca fiind infinit
        for(int i = 1; i <= N; ++i)
            dist[i] = inf;

        G.Dijkstra(1);
    }
    else if(task == 10) // Bellman-Ford
    {
        fin >> N >> M;
        graf G(N, M, 0);
        G.Bellman_Ford(1);
    }
    */

    return 0;
}