#include <bits/stdc++.h>
using namespace std;

#define maxi 100005
#define INF 1e9

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
class Graf
{

    int n,m; //n- nr noduri, m- nr muchii
    int x,y; //muchie stg-dr

    int viz[100005]; //pt dfs
    vector<int> *l;
    vector<pair<int,int>> la[50005]; // list adi  pt dij, bell


public:
    Graf();
    //dfs
    void citireDFS();
    void dfs(int s);
    void nrCompCone();
    //bfs
    int citireBFS();
    void bfs(int s);
    //toposort
    void sort_top_dfs(int s, vector<int>& );
    void citire_top_dfs();
    void sortare_topologica();
    //compTareConexe
    void citire_ctc(vector<int>[],vector<int>[]);
    void dfs1(int s,vector<int>[], vector<int>&,int []);
    void dfs2(int s,vector<int>[], vector<int>[], int [],int);
    void ctc();
    //HAVEL
    void havel_hakimi();
    //PaduriMultDisj
    int find_radacina(int, int[]);
    void unite(int, int, int[], int[]);
    void paduri();
    //dijkstra
    void dijkstra(int[],int[],int);
    void afis_dij();
    //bellmanford
    void bellmanford(int[],int[]);
    void afis_bell();
    //apm
    int apm_find_radacina(int, int[]);
    void apm_unite(int, int, int[], int[]);
    void apm();
    //muchie critica
    void dfs_muchie_crit(int,int,int,int[],int[], vector<pair<int,int>>&);
    void muchie_critica();

    //darb
    void dfs_darb(int,int,int[], int&, int&);
    void afis_darb();

    //royfloyd

    void royfloyd();


};

Graf::Graf()
{
    n = m = x = y = 0;
    l = new vector<int>[maxi];
    //l2 = new vector<int>[maxi];
}

//DFS
void Graf::citireDFS()
{
    in>>n>>m;
    int x,y;
    for(int i =0; i<m; i++)
    {
        in>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
}
void Graf::dfs(int s)
{
    viz[s]=1;
    for(auto el:l[s])
    {
        if(viz[el]==0)
        {
            dfs(el);
        }
    }

}

void Graf::nrCompCone()
{
    int c_con=0;
    for(int i=1; i<=n; i++)
    {
        if(viz[i]==0)
        {
            dfs(i);
            c_con++;
        }
    }
    out<<c_con;
}

//BFS
int Graf::citireBFS()
{
    int s;
    in>>n>>m>>s;

    int x,y;
    for(int i =0; i<m; i++)
    {
        in>>x>>y;
        l[x].push_back(y);
    }
    return s;
}

void Graf::bfs(int s)
{

    //int vizitat[10000];
    queue<int> q;
    int dist[100005];
    for(int i =1; i<=n; i++)
    {
        dist[i]=-1;
    }
    int v;
    q.push(s);
    viz[s] = 1;
    dist[s]=0;
    while(!q.empty())
    {

        v=q.front();
        for(auto el:l[v])
        {

            if(dist[el]==-1)
            {
                q.push(el);
                viz[el]=1;
                dist[el]=dist[v]+1;

            }

        }
        q.pop();
    }


    for(int i = 1; i<=n; i++)
    {

        out << dist[i]<<' ';
    }

}

void Graf::citire_top_dfs()
{
    in>>n>>m;
    int x,y;
    for(int i=0; i<m; i++)
    {
        in>>x>>y;
        l[x].push_back(y);
    }
}
void Graf::sort_top_dfs(int s, vector<int> &sortop)
{

    viz[s]=1;
    for(auto el:l[s])
    {
        if(viz[el]==0)
        {
            sort_top_dfs(el, sortop);
        }

    }
    sortop.push_back(s);
}
void Graf::sortare_topologica()
{
    vector <int> sortop;
    for(int i=1; i<=n; i++)
    {
        if(viz[i]==0)
        {
            sort_top_dfs(i, sortop);
        }
    }
    reverse(sortop.begin(),sortop.end());
    for(int i:sortop)
    {
        out<<i<<" ";
    }
}

//CTC
void Graf::citire_ctc(vector<int>graf1[],vector<int>graf2[])
{


    in>>n>>m;
    int x,y;
    for(int i=0; i<m; i++)
    {
        in>>x>>y;
        graf1[x].push_back(y);
        graf2[y].push_back(x);
    }
}
void Graf::dfs1(int s,vector<int>graf1[], vector<int> &sortop, int viz1[])
{


    viz1[s]=1;
    for(auto el:graf1[s])
    {
        if(viz1[el]==0)
        {
            dfs1(el,graf1, sortop,viz1);
        }

    }
    sortop.push_back(s);
}
void Graf::dfs2(int s,vector<int>graf2[], vector<int> comp[], int viz2[],int comp_curenta)
{


    viz2[s] = 1;
    comp[comp_curenta].push_back(s);
    for(auto el:graf2[s])
    {
        if(viz2[el]==0)
        {
            dfs2(el,graf2,comp,viz2,comp_curenta);
        }
    }
}
void Graf::ctc()
{

    int *viz1 = new int [100005];
    int *viz2 = new int [100005];
    for(int i=0; i<100005; ++i)
    {
        viz1[i]=0;
    }
    for(int i=0; i<100005; ++i)
    {
        viz2[i]=0;
    }


    vector <int> *graf1 = new vector<int>[100005];
    vector <int> *graf2 = new vector<int> [100005];
    int comp_curenta=0;
    vector <int> sortop;
    vector <int> *comp = new vector<int> [100005];

    citire_ctc(graf1,graf2);

    for(int i=1; i<=n; i++)
    {

        if(viz1[i]==0)
        {

            dfs1(i,graf1,sortop,viz1);
        }
    }

    reverse(sortop.begin(),sortop.end());

    for(int i:sortop)
    {
        if(viz2[i]==0)
        {

            dfs2(i,graf2,comp,viz2,comp_curenta);
            comp_curenta++;
        }
    }
    out<<comp_curenta<<'\n';
    for(int i=0; i<comp_curenta; i++)
    {
        for(int j = 0; j < comp[i].size(); j++)
        {
            out<<comp[i][j]<<" ";

        }
        out<<'\n';
    }
}

//HAVEL HAKIMI

void Graf::havel_hakimi()
{
    vector <int> v;
    int from, to;
    in>>n;
    int i;
    for(i=0; i<n; i++)
    {
        int w;
        in>>w;
        v.push_back(w);
    }
    sort(v.begin(), v.end());
    for(from = n-1; from>=0; from--)
    {
        for(to = from -1; to >=0; to--)
        {
            if(v[to]>0 && v[from]>0)
            {
                v[from]--;
                v[to]--;

            }
        }
        if(v[from]>0)
        {
            out<<"Nu";
            break;
        }
        sort(v.begin(), v.begin()+from+1);
    }
    out<<"Da";
}

//Paduri de multimi disjuncte

int Graf::find_radacina(int x, int par[])
{
    vector <int> met;
    while(x!=par[x])  //parcurgem cat timp x are parinte
    {
        x=par[x];
        met.push_back(x);
    }
    for(auto el:met)
    {
        par[el] = x;
    }
    return x;
}

void Graf::unite(int a, int b, int par[], int dim[])
{
    int x = find_radacina(a,par);
    int y = find_radacina(b,par);
    if(dim[x] > dim[y])         //unim arborele mai mic de arborele mai mare
    {
        par[y] = x;
        dim[x]+=dim[y];
    }
    else
    {
        par[x] = y;
        dim[y] += dim[x];
    }

}

void Graf::paduri()
{
    int *par = new int [100005];   // vector pentru parinti
    int *dim = new int [100005];


    int n, m;
    in>> n >> m;

    for(int i=1; i<=n; i++)
    {
        par[i] = i;
    }

    while (m--)
    {
        int cod, a, b;
        in>> cod >> a >> b;
        if(cod == 1)
        {
            unite(a,b,par,dim);
        }
        else
        {
            if(find_radacina(a,par) == find_radacina(b,par))
                out << "DA\n";

            else
                out << "NU\n";
        }
    }

}

//dijkstra


void Graf::dijkstra(int dist[],int vizi[],int s)
{
    dist[s] = 0;
    priority_queue <pair<int,int>> pq;
    pq.push({0, s});

    while (pq.size())
    {
        int from = pq.top().second;

        pq.pop();
        if(vizi[from])
            continue;
        viz[from] = 1;
        for (auto& per: la[from])
        {
            int to = per.first;
            int cost = per.second;

            if (dist[to] > dist[from] + cost)
            {
                dist[to] = dist[from] + cost;
                pq.push({-dist[to], to});
            }
        }
    }
}


void Graf::afis_dij()
{

    int *dist = new int[50005];
    int *vizi = new int[50005];
    int n,m;
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x,y,d;
        in >> x >> y >> d;
        la[x].push_back({y,d});
    }

    for (int i = 1; i <= n; i++)
        dist[i] = INF;

    dijkstra(dist,viz,1);

    for (int i = 2; i <= n; i++)
    {
        if (INF == dist[i])
            dist[i] = 0;
        out<< dist[i] << ' ';
    }
}

//bellmanford

void Graf::bellmanford(int dist[],int vizi[])
{
    dist[1] = 0;
   // bool verif =1;
    priority_queue <pair<int,int>> pq;
    pq.push({0, 1});

    while (pq.size())
    {
        int from = pq.top().second;

        vizi[from] ++;
        if(vizi[from] >= n)
        {
            out<< "Ciclu negativ!";
            //verif =0;
            return;
        }

        pq.pop();                             //il scoate inainte sa se uite la vecinii lui

        for (auto& per: la[from])
        {
            int to = per.first;
            int cost = per.second;

            if (dist[to] > dist[from] + cost)
            {
                dist[to] = dist[from] + cost;
                pq.push({-dist[to], to});
            }
        }
    }





        for (int i = 2; i <= n; i++)
        {
            if (INF == dist[i])             //daca nu exista drum se considera distanta 0
                dist[i] = 0;
            out<< dist[i] << ' ';
        }

}
void Graf::afis_bell()
{
    int *dist = new int[50005];
    int *vizi = new int[50005];
    for(int i=0; i<50005;i++)
    {
        vizi[i]=0;
    }
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x,y,d;
        in >> x >> y >> d;
        la[x].push_back({y,d});

    }

    for (int i = 1; i <= n; i++)
        dist[i] = INF;

    bellmanford(dist,vizi);


}
//apm

int Graf :: apm_find_radacina(int x, int par[])
{
    vector <int> met;
    while(x!=par[x])  //parcurgem cat timp x are parinte
    {
        x=par[x];
        met.push_back(x);
    }
    for(auto el:met)
    {
        par[el] = x;
    }
    return x;
}
void Graf :: apm_unite(int a, int b, int par[], int dim[])
{
    int x = apm_find_radacina(a,par);
    int y = apm_find_radacina(b,par);
    if(dim[x] > dim[y])         //unim arborele mai mic de arborele mai mare
    {
        par[y] = x;
        dim[x]+=dim[y];
    }
    else
    {
        par[x] = y;
        dim[y] += dim[x];
    }
}
void Graf::apm()
{
    int *par = new int [100005];   // vector pentru parinti
    int *dim = new int [100005]; //cat de multe noduri sunt in arborele respectiv
    vector<pair<int,pair<int,int>>> muchii; // m.first -> costul muchiei, m.second.first -> nodul from, m.second.second -> nodul to
    vector<pair<int,int>> muchii_folosite;

    in>> n >> m;
    while(m--)
    {
        pair<int,pair<int,int>> mc; //muchie curenta
        in>>mc.second.first>>mc.second.second>>mc.first; //muchia curenta a fost citita
        muchii.push_back(mc);      //pune muchia curenta in vectorul mare
    }
    sort(muchii.begin(), muchii.end());
    for(int i=1; i<=n; i++)
    {
        par[i] = i;
    }

    int costTotal = 0;
    for(int m = 0; m < muchii.size(); m++)
    {
        if(apm_find_radacina(muchii[m].second.first,par) != apm_find_radacina(muchii[m].second.second,par))  //daca parintii celor doua noduri sunt diferiti
        {

            costTotal +=  muchii[m].first;
            apm_unite(muchii[m].second.first, muchii[m].second.second,par,dim);    //uneste nodurile

            pair<int,int> p;
            p.first = muchii[m].second.first;
            p.second = muchii[m].second.second;       //pune muchiile folosite in vector
            muchii_folosite.push_back(p);
        }
    }

    out << costTotal<<'\n';
    out<<muchii_folosite.size()<<'\n';
    for(int i=0; i<muchii_folosite.size(); i++)
    {

        out<<muchii_folosite[i].first<<" "<<muchii_folosite[i].second<<'\n';
    }
}

//Muchie Critica

void Graf::dfs_muchie_crit(int nodCurent, int parinte, int lv,int lvl[],int low[],vector<pair<int,int>>& critice )
{
    lvl[nodCurent]=lv;
    low[nodCurent]=lv;
    for(auto vecin : l[nodCurent])
    {
        if(lvl[vecin]==0)
        {
            dfs_muchie_crit(vecin,nodCurent,lv+1,lvl,low,critice);
            low[nodCurent]=min(low[nodCurent],low[vecin]);

        }
        else if(vecin!=parinte)
        {
            low[nodCurent]=min(low[nodCurent],lvl[vecin]);
        }
    }
    if(low[nodCurent]==lvl[nodCurent]&& parinte!=-1)
    {
        critice.push_back({nodCurent,parinte});
    }
}
void Graf::muchie_critica()
{
    int *low=new int[100005];
    int *lvl=new int[1000005];
    vector<pair<int,int>> critice;
    int vecin,nodCurent,lv,nrNoduri,nrMuchii;
    in>>nrNoduri>>nrMuchii;

    int x,y;
    for(int i =0; i<nrMuchii; i++)
    {
        in>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    dfs_muchie_crit(1,-1,1,lvl,low,critice);
    for(auto& per:critice)
    {
        out<<per.first<<' '<<per.second<<'\n';
    }
}

//darb  -nr noduri dintre cele mai departate frunze
void Graf::dfs_darb(int nod, int nivel, int vizitat[], int& nivelMaxim, int& pozitieNivel )
{
    vizitat[nod] = 1; //nod curent
    if(nivel >= nivelMaxim)
    {
        nivelMaxim=nivel;
        pozitieNivel=nod;

    }
    for(auto el:l[nod])
    {
        if(vizitat[el]==0)
        {
            dfs_darb(el,nivel+1,vizitat,nivelMaxim,pozitieNivel);
        }
    }
}
void Graf::afis_darb()
{
    int s;
    int *vizitat=new int[100005];
    int nivelMaxim, pozitieNivel;

    int x,y;
    in>>n;
    for(int i=0;i<n;++i)
    {
        in>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }

    dfs_darb(1,0,vizitat,nivelMaxim,pozitieNivel);

    for(int i = 0; i<n; ++i)
    {
        vizitat[i]=0;
    }

    dfs_darb(pozitieNivel, 0,vizitat,nivelMaxim,pozitieNivel);

    out<<nivelMaxim+1;
}

//Royfloyd



void Graf::royfloyd()
{
    int a[105][105];

    in>>n;
    for(int i =1;i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            in>>a[i][j];
            if(i!=j && a[i][j]==0)
            {
                a[i][j] = INF;            //elementele de pe diagonale sunt 0(self loop),
            }                              //iar daca nu exista muchie se retine ca infinit
        }
    }

    for(int k =1; k<=n; k++)               //nod intermediar intre alte doua noduri( i < k <  j)
    {
        for(int i=1; i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][k] && a[k][j])
                {
                    a[i][j] = min(a[i][j], a[i][k] + a[k][j]);    //cost = min dintre costul actual si suma dintre intermediar si noduri
                }
            }
        }
    }
    //afis
     for(int i =1; i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            out<<a[i][j]<<" ";
        }
        out<<'\n';
    }
}

int main()
{
    //Royfloyd

    //Graf g12;
    //g12.royfloyd();

    //Darb

    //Graf g11;
    //g11.afis_darb();

    //Mcrit

/*  Graf g10;
    g10.muchie_critica();*/
//APM

    //Graf g9;
    // g9.apm();

//Bellmanford

    Graf g8;
    g8.afis_bell();

//Dijktra

    //Graf g7;
    //g7.afis_dij();

//Paduri
    /*
       Graf g6;
       g6.paduri();

    //HAVEL
       Graf g4;
       g4.havel_hakimi();
    */
    /*
    //CTC
       Graf g5;
       g5.ctc();
       */
    /*
    //SORTOP

     Graf g3;
     g3.citire_top_dfs();
     g3.sortare_topologica();
     */

    /*
    //BFS
     int ss; //stocheaza ce returneaza citirea (nodul s initial)
     Graf g2;
     ss=g2.citireBFS();
     g2.bfs(ss);
    */


    /*
    //DFS
    Graf g1;
    g1.citireDFS();

    g1.nrCompCone();
    */
    return 0;
}