#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <utility>
#include <queue>
using namespace std;

class Graf{
    int nr_noduri;
    vector < vector < int > > lista_vecini;
    vector < vector < int > > lista_muchii;
    vector < vector < pair < int, int > > > lista_vecini_cost;
public:
    Graf();
    Graf( int nr_noduri1, vector < vector < int > > lista_vecini1 );
    Graf( const Graf &ob );
    Graf &operator = ( Graf &ob );
    ~Graf(){};
    void adauga_muchie(int intrare, int iesire);
    void adauga_nod();
    void adauga_muchie_cost(int intrare, int iesire, int cost);
    friend istream &operator >> ( istream &in, Graf &ob );
    friend ostream &operator << ( ostream &out, Graf &ob );
    vector < int > bfs(int start);
    int dfs();
    void vizitat(vector < int > &culoare, vector < int > &d, vector < int > &f, int &u, int &timp);
    void strongconnect(int v,int &index, vector <int> &indexv,vector <int> &lowlink,vector <bool> &on_stack, deque <int> &S, vector < vector < int > > &componente);
    vector < vector < int > > ctc();
    void dfs_bi( int k, int tata, vector < int > &v, vector < int > &nivel, vector < int > &nma, deque < int > &s, vector < vector < int > > &bic );
    vector < vector < int > > biconex();
    vector < int > sortaret();
    void dfs_muchii( int k, int tata, vector < int > &v, vector < int > &nivel, vector < int > &nma );
    void muchii_critice();
    void Hakimi();
    void quicksort( int inf, int sup );
    int reprez( vector < int > &ind, int i );
    void reuniune( vector < int > &ind, int i, int j );
    vector < vector < int > > apm();
    int find(int x, vector < int > &t);
    void unite(int x, int y, vector < int > &rang, vector < int > &t);
    void disjoint();
    vector < int > BellmanFord( int nod_pornire );
    void BellmanFord();
    void Dijkstra(int nod_pornire, int n, vector < int > &distante);
    void Dijkstra();
    int BF(int N, int viz[1010], int coad[1010], vector < int > g[1010], int tata[1010], int flux[101][101], int c[101][101], int act, int Q);
    void Flux_maxim();
    void roy_floyd(int n, int a[105][105]);
    void main_roy_floyd();
    void dfs14(int x, int d, vector < int > &viz, vector < int > &dist);
    pair < int, int > getMaxDist(vector < int > &dist);
    void clear(vector < int > &viz, vector < int > &dist);
    void diametru();
};

Graf :: Graf(){
    nr_noduri = -1;
}
Graf :: Graf( int nr_noduri1, vector < vector < int > > lista_vecini1 ){
    nr_noduri = 0;
    for( int i = 0; i < lista_vecini1.size(); i++ ){
        lista_vecini.push_back(lista_vecini1[i]);
    }
}
Graf :: Graf( const Graf &ob ){
    nr_noduri = ob.nr_noduri;
    for( int i = 0; i < ob.lista_vecini.size(); i++ ){
        lista_vecini.push_back(ob.lista_vecini[i]);
    }
}
Graf &Graf::operator = ( Graf &ob ){
    if( this != &ob ){
        nr_noduri = ob.nr_noduri;
        for( int i = 0; i < ob.lista_vecini.size(); i++ ){
            lista_vecini.push_back(ob.lista_vecini[i]);
        }
    }
    return *this;
}
ostream &operator << (ostream &out, Graf &ob){
    out << "Numar noduri: " << ob.nr_noduri << endl;
    out << "Muchii: " << endl;
    for( int i = 0; i < ob.lista_vecini.size(); i++ ){
        for( int j = 0; j < ob.lista_vecini[i].size(); j++ ){
            out << i << " " << ob.lista_vecini[i][j] << endl;
        }
    }
    return out;
}
void Graf::adauga_nod(){
    vector < int > v;
    lista_vecini.push_back(v);
    vector < pair < int,int > > x(1,make_pair(-1,-1));
    lista_vecini_cost.push_back(x);
    nr_noduri++;
}
void Graf::adauga_muchie(int intrare, int iesire){
    lista_vecini[intrare].push_back(iesire);
}
void Graf::adauga_muchie_cost(int intrare, int iesire, int cost){
    vector < int > muchie;
    muchie.push_back(intrare);
    muchie.push_back(iesire);
    muchie.push_back(cost);
    lista_muchii.push_back(muchie);
    lista_vecini_cost[intrare].push_back(make_pair(iesire,cost));
};

//problema 1 bfs-100pct
vector < int > Graf::bfs(int start){
    vector < int > culoare, d;
    for( int i = 0; i <= nr_noduri; i++ ){
        if( i != start ){
            culoare.push_back(0);
            d.push_back(-1);
        }
        else{
            culoare.push_back(1);
            d.push_back(0);
        }
    }
    deque < int > Q;
    Q.push_back(start);

    int u;
    while( Q.size() != 0 ){
        u = Q[0];
        for( int i = 0; i < lista_vecini[u].size(); i++ ){
            if( culoare[ lista_vecini[u][i]] == 0 ){
                culoare[ lista_vecini[u][i] ] = 1;
                d[ lista_vecini[u][i] ] = d[u] + 1;
                Q.push_back( lista_vecini[u][i] );
            }
        }
        Q.pop_front();
        culoare[u] = 2;
    }
    return d;
}

//problema2 dfs-100pct
int Graf::dfs(){
    vector < int > culoare, d, f;
    for( int i = 0; i <= nr_noduri; i++ ){
        culoare.push_back(0);
        d.push_back(-1);
        f.push_back(-1);
    }
    int timp = 0;
    int contor = 0;
    for( int i = 1; i <= nr_noduri; i++ ){
        if( culoare[i] == 0 ){
            contor++;
            Graf::vizitat(culoare, d, f, i,timp);
        }
    }
    return contor;
}
void Graf::vizitat(vector < int > &culoare, vector < int > &d, vector < int > &f, int &u, int &timp){
    culoare[u] = 1;
    timp++;
    d[u] = timp;
    for( int i = 0; i < lista_vecini[u].size(); i++ ){
        if( culoare[ lista_vecini[u][i] ] == 0 ){
            Graf::vizitat(culoare,d,f,lista_vecini[u][i],timp);
        }
    }
    culoare[u] = 2;
    timp++;
    f[u] = timp;
}

//problema3 biconex-100pct
void Graf::dfs_bi( int k, int tata, vector < int > &v, vector < int > &nivel, vector < int > &nma, deque < int > &s, vector < vector < int > > &bic ){
    v[k] = 1;
    s.push_front(k);
    if( tata == -1 ){
        nivel[k] = 1;
    }
    else nivel[k] = nivel[tata] + 1;
    nma[k] = nivel[k];
    for( int i = 0; i < lista_vecini[k].size(); i++ ){
        int x;
        x = lista_vecini[k][i];
        if( x != tata ){
            if( v[x] == 1 ){
                if( nma[k] > nivel[x] ){
                    nma[k] = nivel[x];
                }
            }
            else{
                dfs_bi(x, k, v, nivel, nma, s, bic);
                if( nma[k] > nma[x] ){
                    nma[k] = nma[x];
                }
                if( nivel[k] <= nma[x] ){
                    vector < int > conex;
                    while( s[0] != x ){
                        conex.push_back(s[0]);
                        s.pop_front();
                    }
                    conex.push_back(x);
                    s.pop_front();
                    conex.push_back(k);
                    bic.push_back(conex);
                }
            }
        }
    }
}
vector < vector < int > > Graf::biconex(){
    vector < int > v, nivel,nma;
    vector < vector < int > > bic;
    deque < int > s;
    for( int i = 0; i <= nr_noduri; i++ ){
        nivel.push_back(0);
        nma.push_back(0);
        v.push_back(0);
    }
    dfs_bi( 1, -1, v, nivel, nma, s, bic );
    return bic;
}

//problema4 ctc-100pct

void Graf::strongconnect(int v,int &index, vector <int> &indexv,vector <int> &lowlink,vector <bool> &on_stack, deque <int> &S, vector < vector < int > > &componente){
    indexv[v] = index;
    lowlink[v] = index;
    index++;
    S.push_front(v);
    on_stack[v] = 1;
    int w;
    for( int i = 0; i < lista_vecini[v].size(); i++ ){
        w = lista_vecini[v][i];
        if( indexv[w] == -1 ){
            strongconnect(w, index,indexv,lowlink,on_stack,S,componente);
            if( lowlink[ w ] < lowlink[v] ){
                lowlink[v] = lowlink[w];
            }
        }
        else{
            if( on_stack[w] == 1 ){
                if( indexv[ w ] < lowlink[v] ){
                        lowlink[v] = indexv[ w ];
                }
            }
        }
    }
    if( lowlink[v] == indexv[v] ){
        vector < int > componenta;
        do{
            w = S[0];
            S.pop_front();
            on_stack[w] = 0;
            componenta.push_back(w);
        }while( w != v );
        componente.push_back(componenta);
    }
}
vector < vector < int > > Graf::ctc(){
    vector < int > indexv, lowlink;
    vector < bool > on_stack;
    vector < vector < int > > componente;
    deque < int > S;
    int index = 0;
    indexv.push_back(0);
    lowlink.push_back(0);
    on_stack.push_back(0);
    for(int i = 0; i < nr_noduri; i++){
        indexv.push_back(-1);
        lowlink.push_back(0);
        on_stack.push_back(0);
    }
    for( int i = 1; i <= nr_noduri; i++ ){
        if( indexv[i] == -1 ){
            strongconnect(i,index,indexv,lowlink,on_stack,S, componente);
        }
    }
    return componente;
}

//problema5 sortaret-100pct
vector < int > Graf::sortaret(){
    deque < int > sortare;
    vector < int > grade(nr_noduri+1);
    vector < vector < int > > vecini1;
    for( int i = 0; i <= lista_vecini.size(); i++ ){
        vector < int > v;
        vecini1.push_back(v);
    }
    for( int i = 0; i < lista_vecini.size(); i++ ){
        for( int j = 0; j < lista_vecini[i].size(); j++ ){
            vecini1[lista_vecini[i][j]].push_back(i);
        }
    }
    grade[0] = -1;
    for( int i = 1; i <= nr_noduri; i++ ){
        grade[i] = vecini1[i].size();
        if( vecini1[i].size() == 0 ){
            sortare.push_back(i);
        }
    }
    vector < int > sortare_lista;
    while( sortare.size() != 0 ){
        int nr = sortare[0];
        sortare_lista.push_back(nr);
        sortare.pop_front();
        for( int i = 0; i < lista_vecini[nr].size(); i++ ){
            grade[lista_vecini[nr][i]]--;
            if( grade[ lista_vecini[nr][i] ] == 0 ){
                sortare.push_back( lista_vecini[nr][i] );
            }
        }
    }
    return sortare_lista;
}

//problema6 hakimi-100pct
void Graf::Hakimi(){
    int nr_noduri;
    deque < int > grade;
    deque < int > nr_ordine;
    int suma = 0, ok = 1;
    cout << "Introduceti numarul de noduri: ";
    cin >> nr_noduri;
    vector < vector < int > > vecini(nr_noduri+1);
    cout << "Introduceti gradele nodurilor: ";
    for( int i = 1; i <= nr_noduri; i++ ){
        int grad;
        cin >> grad;
        grade.push_back(grad);
        nr_ordine.push_back(i);
        suma = suma + grad;
        if( grad > nr_noduri-1 ) ok = 0;
    }
    if( suma % 2 == 1 ) ok = 0;
    if( ok == 0 ){
        cout << "Nu se poate obtine un graf";
    }
    else{
        //sortare descrescatoare
        for( int i = 0; i < grade.size(); i++ ){
            for( int j = 0; j < i; j++ ){
                if( grade[i] > grade[j] ){
                    int aux;
                    aux = grade[i];
                    grade[i] = grade[j];
                    grade[j] = aux;
                    aux = nr_ordine[i];
                    nr_ordine[i] = nr_ordine[j];
                    nr_ordine[j] = aux;
                }
            }
        }
        while( grade[0] != 0 || grade[ grade.size()-1 ] < 0 ){
            //salvam datele pentru gradul cel mai mare si il eliminam
            int dk = grade[0];
            int nod = nr_ordine[0];
            grade.pop_front();
            nr_ordine.pop_front();
            //afisam muchiile
            for( int i = 0; i < dk; i++ ){
                vecini[nod].push_back(nr_ordine[i]);
                grade[i]--;
            }
            //resortam descrescator
            for( int i = 0; i < grade.size(); i++ ){
                for( int j = 0; j < i; j++ ){
                    if( grade[i] > grade[j] ){
                        int aux;
                        aux = grade[i];
                        grade[i] = grade[j];
                        grade[j] = aux;
                        aux = nr_ordine[i];
                        nr_ordine[i] = nr_ordine[j];
                        nr_ordine[j] = aux;
                    }
                }
            }
        }
        if( grade[0] == 0 && grade[grade.size()-1] >= 0 ){
            cout << "Muchii: " << endl;
            for( int i = 0; i < vecini.size(); i++ ){
                for( int j = 0; j < vecini[i].size(); j++ ){
                    cout << i << " " << vecini[i][j] << endl;
                }
            }
        }
        else{
            cout << "Nu se poate construi acest graf";
        }
    }
}

//problema7 muchii_critice-100pct
void Graf::dfs_muchii( int k, int tata, vector < int > &v, vector < int > &nivel, vector < int > &nma ){
    v[k] = 1;
    if( tata == -1 ){
        nivel[k] = 1;
    }
    else nivel[k] = nivel[tata] + 1;
    nma[k] = nivel[k];
    for( int i = 0; i < lista_vecini[k].size(); i++ ){
        int x;
        x = lista_vecini[k][i];
        if( x != tata ){
            if( v[x] == 1 ){
                if( nma[k] > nivel[x] ){
                    nma[k] = nivel[x];
                }
            }
            else{
                dfs_muchii(x, k, v, nivel, nma);
                if( nma[k] > nma[x] ){
                    nma[k] = nma[x];
                }
                if( nivel[k] < nma[x] ){
                    cout << k << " " << x << endl;
                }
            }
        }
    }
}
void Graf::muchii_critice(){
    vector < int > nivel, nma, v;
    for( int i = 0; i < nr_noduri; i++ ){
        nivel.push_back(0);
        nma.push_back(0);
        v.push_back(0);
    }
    dfs_muchii( 0, -1, v, nivel, nma);
}

//problema8 apm-100pct
void Graf::quicksort( int inf, int sup ){
    int i, j, x;
    vector < int > t;
    i = inf;
    j = sup;
    x = lista_muchii[(i+j)/2][2];
    do{
        while( i < sup && lista_muchii[i][2] < x ) i++;
        while( j > inf && lista_muchii[j][2] > x ) j--;
        if( i <= j ){
            t = lista_muchii[i];
            lista_muchii[i] = lista_muchii[j];
            lista_muchii[j] = t;
            i++;
            j--;
        }
    }while( i <= j );
    if( inf < j ) quicksort( inf, j );
    if( i < sup ) quicksort( i, sup );
}
int Graf::reprez( vector < int > &ind, int i ){
    if( ind[i] == i ) return i;
    ind[i] = reprez( ind, ind[i] );
    return ind[i];
}
void Graf::reuniune( vector < int > &ind, int i, int j ){
    ind[reprez(ind,i)] = reprez(ind,j);
}
vector < vector < int > > Graf::apm(){
	vector <vector < int > > apm;
    quicksort(0,lista_muchii.size()-1);
    vector < int > ind;
    for( int i = 0; i <= nr_noduri; i++ ){
        ind.push_back(i);
    }
    int nrmsel = 0;
    int suma = 0;
    for( int i = 0; i < lista_muchii.size(); i++ ){
        if( reprez(ind, lista_muchii[i][0]) != reprez(ind, lista_muchii[i][1]) ){
            apm.push_back(lista_muchii[i]);
            suma += lista_muchii[i][2];
            reuniune(ind, lista_muchii[i][0], lista_muchii[i][1]);
            nrmsel++;
            if(nrmsel == nr_noduri - 1){
                break;
            }
        }
    }
    return apm;
}

//problema9 disjoint-100pct
int Graf::find(int x, vector < int > &t){
    int r, y;
    //merg in subgraf pana la radacina
    for( r = x; t[r] != r; r = t[r] );
    for(x = x; t[x] != x; x = t[x] ){
        y = t[x];
        t[x] = r;
        x = y;
    }
    return r;
}
void Graf::unite(int x, int y, vector < int > &rang, vector < int > &t){
    if( rang[x] > rang[y] ){
        t[y] = x;
    }
    else t[x] = y;
    if( rang[x] == rang[y] ) rang[y]++;
}
void Graf::disjoint(){
    int x, y, operatie;
    int n, m;
    cin >> n >> m;
    vector < int > t;
    vector < int > rang;
    rang.push_back(-1);
    t.push_back(0);
    for( int i = 1; i <= n; i++ ){
        t.push_back(i);
        rang.push_back(1);
    }
    for( int i = 1; i <= m; i++ ){
        cin >> operatie >> x >> y;
        if( operatie == 2 ){
            if( find(x,t) == find(y,t) ) cout << "DA" << "\n";
            else cout << "NU" << "\n";
        }
        else{
            unite(find(x,t), find(y,t),rang,t);
        }
    }
}

//problema10 bellman-ford-100pct
vector < int > Graf::BellmanFord( int nod_pornire ){
    vector < pair < int,int > > x(1,make_pair(-1,-1));
    lista_vecini_cost.push_back(x);
    vector < int > distante(nr_noduri+1, 9999999);
    vector < int > vizitat(nr_noduri+1, 0);
    vector < int > apartineCoada(nr_noduri+1, 0);
    queue < int > coada;
    int faraNeg = 1;

    coada.push(nod_pornire);
    apartineCoada[nod_pornire] = 1;
    distante[nod_pornire] = 0;
    while( !coada.empty() && faraNeg ){
        int x = coada.front();
        coada.pop();
        apartineCoada[x] = 0;

        for( int i = 1; i < lista_vecini_cost[x].size(); i++ ){
            if( distante[x] + lista_vecini_cost[x][i].second < distante[ lista_vecini_cost[x][i].first ] ){
                distante[ lista_vecini_cost[x][i].first ] = distante[x] + lista_vecini_cost[x][i].second; //relaxam
                vizitat[ lista_vecini_cost[x][i].first ]++;

                if( !apartineCoada[ lista_vecini_cost[x][i].first ] ){
                    coada.push(lista_vecini_cost[x][i].first);
                    apartineCoada[lista_vecini_cost[x][i].first] = 1;
                }

                if( vizitat[ lista_vecini_cost[x][i].first ] >= nr_noduri ){
                    faraNeg = 0;
                }
            }
        }
    }
    if( faraNeg == 0 ){
        vector < int > lista_goala;
        return lista_goala;
    }
    return distante;
}
void Graf::BellmanFord(){
    vector < int > distante = BellmanFord(1);
    if( distante.size() != 0 ){
        for( int i = 2; i <= nr_noduri; i++ ){
            cout << distante[i] << " ";
        }
    }
    else{
        cout << "Ciclu negativ!";
    }
    cout << endl;
}

//problema11 dijkstra-100pct
void Graf::Dijkstra(int nod_pornire, int n, vector < int > &distante){
    priority_queue < pair < int, int >, vector < pair <int, int> >, greater < pair < int, int > > > coada_prioritati;
    vector < int > apartine_Coada(n+1, 0);
    coada_prioritati.push(make_pair(0,nod_pornire));
    distante[nod_pornire] = 0;
    while( coada_prioritati.size() != 0 ){
        int x = coada_prioritati.top().second;
        coada_prioritati.pop();
        if( apartine_Coada[x] == 0 ){
            apartine_Coada[x] = 1;
            for( int i = 1; i < lista_vecini_cost[x].size(); i++ ){
                if( distante[ lista_vecini_cost[x][i].first ] > distante[x] + lista_vecini_cost[x][i].second ){
                    distante[ lista_vecini_cost[x][i].first ] = distante[x] + lista_vecini_cost[x][i].second;
                    coada_prioritati.push(make_pair(distante[lista_vecini_cost[x][i].first ], lista_vecini_cost[x][i].first));
                }
            }
        }
    }
}
void Graf::Dijkstra(){
    vector < int > distante(nr_noduri+1, 999999);
    Dijkstra(1,nr_noduri,distante);
    for( int i = 2; i <= nr_noduri; i++ ){
        if( distante[i] == 999999 ) cout << 0 << " ";
        else cout << distante[i] << " ";
    }
    cout << endl;
}

//problema12 flux_maxim-100p

int Graf::BF(int N, int viz[1010], int coad[1010], vector < int > g[1010], int tata[1010], int flux[101][101], int c[101][101], int act, int Q){
    for( int i = 1; i <= N; i++ ){
        viz[i] = 0;
    }

    coad[0] = 1;
    int st = 0, dr = 1;
    viz[1] = 1;

    while( st <dr ){
        act = coad[st];
        if( act != N ){
            for( int i = 0; i< g[act].size(); i++ ){
                Q = g[act][i];
                if( c[act][Q] == flux[act][Q] || viz[Q] ){
                    continue;
                }
                viz[Q] = 1;
                coad[dr++] = Q;
                tata[Q] = act;
            }

        }
        st++;
    }
    return viz[N];
}
void Graf::Flux_maxim(){
    int flux[101][101];
    int c[101][101];
    int tata[1010];
    int viz[1010], flow;
    int coad[1015];
    int Q, x, y, z, N, act, M, fmin;
    vector < int > g[1010];
    cout << "Introduceti numarul de noduri si numarul de muchii: ";
    cin >> N >> M;
    for( int i = 1; i <= M; i++ ){
        cout << "Introduceti muchia cu numarul " << i << ": ";
        cin >> x >> y >> z;
        c[x][y] += z;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for( flow = 0; BF(N, viz, coad, g, tata, flux, c, act, Q); ){
        for( int i = 0;i < g[N].size(); i++ ){
            act = g[N][i];
            if( flux[act][N] == c[act][N] || !viz[act] ){
                continue;
            }
            tata[N] = act;
            fmin = 10101000;
            for( int nod = N; nod != 1; nod = tata[nod] ){
                fmin = min( fmin, c[tata[nod] ][nod] - flux[tata[nod] ][nod] );
            }
            if( fmin == 0 ){
                continue;
            }
            for( int nod = N; nod != 1; nod = tata[nod] ){
                flux[ tata[nod] ][nod] += fmin;
                flux[ nod ][ tata[nod] ] -= fmin;
            }
            flow += fmin;
        }
    }
    cout << flow << endl << endl;
}

//problema13 roy_floyd-100p
void Graf::roy_floyd(int n, int a[105][105]){
    for( int k = 1; k <= n; k++ ){
        for( int i = 1; i <= n; i++ ){
            for( int j = 1; j <= n; j++ ){
                if (a[i][k] && a[k][j] && (a[i][j] > a[i][k] + a[k][j] || !a[i][j]) && i != j) a[i][j] = a[i][k] + a[k][j];
            }
        }
    }
}
void Graf::main_roy_floyd(){

    int a[105][105], n;

    cin >> n;
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= n; j++ ){
            cin >> a[i][j];
        }
    }

    roy_floyd(n,a);

    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j <= n; j++ ){
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
}

//problema14 diametrul unui arbore-100p

void Graf::dfs14(int x, int d, vector < int > &viz, vector < int > &dist){
    viz[x] = 1;
    dist[x] = d;
    for( auto n : lista_vecini[x] ){
        if( viz[n] == 0 ){
            dfs14(n, d+1,viz,dist);
        }
    }
}
pair < int, int > Graf::getMaxDist(vector < int > &dist){
    int distMax = 0;
    int nod = 0;
    for( int i = 1; i <= nr_noduri; i++ ){
        if( dist[i] > distMax ){
            distMax = dist[i];
            nod = i;
        }
    }
    return make_pair(distMax, nod);
}
void Graf::clear(vector < int > &viz, vector < int > &dist){
    for( int i = 1; i <= nr_noduri; i++ ){
        viz[i] = 0;
        dist[i] = 0;
    }
}
void Graf::diametru(){

    vector < int > dist;
    vector < int > viz;

    dist.resize(nr_noduri+1);
    viz.resize(nr_noduri+1);
    dfs14(1,0, viz, dist);
    pair<int,int> maxAndNod = getMaxDist(dist);
    clear(viz,dist);
    int n1 = maxAndNod.second;
    dfs14(maxAndNod.second,0, viz, dist);
    maxAndNod = getMaxDist(dist);
    cout << maxAndNod.first+1 << endl;
}

int main(){
//https://infoarena.ro/problema/bfs

/*
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    Graf x;
    int n, m, start;
    fin >> n >> m >> start;
    for( int i = 0; i <= n; i++ ){
        x.adauga_nod();
    }
    for( int i = 0; i < m; i++ ){
        int intrare, iesire;
        fin >> intrare >> iesire;
        x.adauga_muchie(intrare, iesire);
    }
    vector < int > sol_bfs = x.bfs(start);
    for( int i = 1; i <= n; i++ ){
        fout << sol_bfs[i] << " ";
    }
*/

//https://infoarena.ro/problema/dfs

/*
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    Graf x;
    int n, m;
    fin >> n >> m;
    for( int i = 0; i <= n; i++ ){
        x.adauga_nod();
    }
    for( int i = 0; i < m; i++ ){
        int intrare, iesire;
        fin >> intrare >> iesire;
        x.adauga_muchie(intrare, iesire);
        x.adauga_muchie(iesire,intrare);
    }
    fout << x.dfs();
*/

//https://infoarena.ro/problema/biconex
/*
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    Graf x;
    int n, m;
    fin >> n >> m;
    for( int i = 0; i <= n; i++ ){
        x.adauga_nod();
    }
    for( int i = 0; i < m; i++ ){
        int intrare, iesire;
        fin >> intrare >> iesire;
        x.adauga_muchie(intrare, iesire);
        x.adauga_muchie(iesire,intrare);
    }
    vector < vector < int > > sol_biconex = x.biconex();
    fout << sol_biconex.size() << '\n';
    for( int i = 0; i < sol_biconex.size(); i++ ){
        for( int j = 0; j < sol_biconex[i].size(); j++ ){
            fout << sol_biconex[i][j] << " ";
        }
        fout << '\n';
    }
*/


//https://infoarena.ro/problema/ctc
/*
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    Graf x;
    int n, m;
    fin >> n >> m;
    for( int i = 0; i <= n; i++ ){
        x.adauga_nod();
    }
    for( int i = 0; i < m; i++ ){
        int intrare, iesire;
        fin >> intrare >> iesire;
        x.adauga_muchie(intrare, iesire);
    }
    vector < vector < int > > sol_ctc = x.ctc();
    fout << sol_ctc.size() << '\n';
    for( int i = 0; i < sol_ctc.size(); i++ ){
        for( int j = 0; j < sol_ctc[i].size(); j++ ){
            fout << sol_ctc[i][j] << " ";
        }
        fout << '\n';
    }

//https://infoarena.ro/problema/sortaret
/*
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    Graf x;
    int n, m;
    fin >> n >> m;
    for( int i = 0; i <= n; i++ ){
        x.adauga_nod();
    }
    for( int i = 0; i < m; i++ ){
        int intrare, iesire;
        fin >> intrare >> iesire;
        x.adauga_muchie(intrare, iesire);
    }
    vector < int > sol_sortaret = x.sortaret();
    for( int i = 0; i < sol_sortaret.size(); i++ ){
        fout << sol_sortaret[i] << " ";
    }
*/

//https://infoarena.ro/problema/apm
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    Graf x;

    int n, m;
    fin >> n >> m;

    for( int i = 0; i <= n; i++ ){
        x.adauga_nod();
    }
    for( int i = 0; i < m; i++ ){
        int intrare, iesire, cost;
        fin >> intrare >> iesire >> cost;
        x.adauga_muchie_cost(intrare,iesire,cost);
        x.adauga_muchie_cost(iesire,intrare,cost);
    }
    vector < vector < int > > apm_solutie = x.apm();

    int suma = 0;
    for( int i = 0; i < apm_solutie.size(); i++ ){
        suma += apm_solutie[i][2];
    }
    fout << suma << '\n' << n-1 << '\n';

    for( int i = 0; i < apm_solutie.size(); i++ ){
        for( int j = 0; j < apm_solutie[i].size(); j++ ){
            fout << apm_solutie[i][j] << " ";
        }
        fout << '\n';
    }
}