#include <iostream>
#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");



typedef struct muu
{
    int varf1;
    int varf2;
    int cost;

} muchie;

typedef struct g
{
    vector<muchie> muchii;
    vector<int> varfuri;
    int cost_total;

} graf;

bool comparator ( const muchie& m1 , const muchie& m2)
{
    return m1.cost < m2.cost;
}

unordered_map<int,int> parinti;
unordered_map<int,int> adancime;

void fa_seturi();
int cauta_set( int nod );
void uneste ( int set1 , int set2 );

graf gi;
graf rezultat;

int nr_noduri;
int nr_muchii;

void citeste_graf(graf gui);
void afisea_muchii(graf gui);
void kruskal( graf gui );

int main()
{
    rezultat.cost_total = 0;
    cout << "Hello world!" << endl;
    citeste_graf(gi);
    fa_seturi();
    sort(gi.muchii.begin() , gi.muchii.end() , comparator);
    kruskal(gi);

    g << rezultat.cost_total << endl;
    int nr_muchii2 = (int)rezultat.muchii.size();
    g << nr_muchii2 << endl;
    for(  int  i = 0 ; i < nr_muchii2 ; i++ )
        g << rezultat.muchii[i].varf1 << " " << rezultat.muchii[i].varf2 << endl;

    g.close();
    f.close();
    return 0;
}
void kruskal(graf gui )
{
    int set1,set2;
    muchie aux;
    for( int i = 0 ; i < nr_muchii ; i++ )
    {

         set1 = cauta_set( gui.muchii[i].varf1 );
         set2 = cauta_set( gui.muchii[i].varf2 );
         if( set1 != set2 )
         {
             uneste(set1 , set2 );
             aux = gui.muchii[i];
             rezultat.muchii.push_back( aux );
             rezultat.cost_total += gui.muchii[i].cost;
         }
    }
}

void uneste( int set1 , int set2 )
{
    if( adancime[ set1 ] ==  adancime[ set2 ] )
    {
        parinti[ set1 ] = set2;
        adancime [ set2 ]++ ;
    }

    else  if (  adancime[ set1 ] > adancime[ set2 ] )

         {
             parinti[set2 ] = set1;
             adancime[ set1 ] += (adancime[ set1 ] - adancime[set2 ];
         }
        else
        {
            parinti[ set1 ] = set2;
            adancime[ set2 ] += (adancime[ set2 ] - adancime[set1 ]);
        }


}

int cauta_set( int nod )
{
    if ( parinti[ nod ] == nod )
        return nod;
    else return cauta_set( parinti[nod] );
}

void fa_seturi()
{
    for( int i = 1; i <= nr_noduri ;i++ )
    {
        parinti[ i ] = i;
        adancime[ i ] = 0;
    }
}

void afisea_muchii(graf gui)
{
    for( int i = 0 ; i < nr_muchii ; i++ )
    {
        cout<<gui.muchii[i].varf1<<" "<<gui.muchii[i].varf2 << " -- " << gui.muchii[i].cost << endl;
    }
}

void citeste_graf(graf gui)
{
    f >> nr_noduri >> nr_muchii;
    muchie aux;
    for( int i = 0; i <  nr_muchii ; i++ )
    {
        f >> aux.varf1 >> aux.varf2 >> aux.cost;
        gi.muchii.push_back( aux );
    }
}