#include <iostream>
#include <fstream>

using namespace std;
const int maxn = 200001;
const int maxm = 400001;
int N,M;
const int inf = 1<<30;
const int linf = -2000;

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

typedef struct muchie
{
    int x,y,cost;
} m;

typedef struct a
{
    int nod;
    int cost;
    a* next;
} adi;

adi* lista_a[maxn];

m muchii[maxm];
int tata[maxn], viz[maxn];
int h[maxn] , d[maxn] , p[maxn] , dim_h;
int S,NR;

void schimba(  int x , int y )
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

void bubble_down(int index);
void bubble_up( int index );
void adauga_in_a(int x , int y, int z );
void citeste();
void PRIM();

int main()
{
    cout << "Hello world!" << endl;
    citeste();
    PRIM();

    g << S << "\n" << NR << "\n";
    for( int i = 1; i <= NR ; i++ )
        g<< muchii[i].x << " "<<  muchii[i].y<<"\n";
    return 0;
}

void PRIM()
{
    for ( int i = 1; i <= N ; i++ )
    {
        p[ i ] = -1;
        d[i] = inf;
        tata[i]= 0;
    }

    h[++dim_h] = 1;
    p[ h[1] ] = 1;
    d[ h[1] ] = 0;
    while( dim_h )
    {
        int mini = h[1];
        schimba( 1, dim_h );
        p[ h[1] ] = 1;
        --dim_h;

        bubble_down(1);


        if  ( tata[mini] != 0  )
            {
                S+= d[mini];
                muchii[++NR].x = mini;
                muchii[NR].y = tata[mini];
                muchii[NR].cost = d[mini];
            }

        adi* aux =  lista_a[mini];
        int x= aux->cost;

        while( aux )
        {

            if( d[ aux->nod ] > aux->cost )
            {
                d[ aux->nod ] =  aux->cost;
                tata[ aux->nod ] = mini;
                if( p[ aux->nod ] != -1 )
                {
                    bubble_up( p[ aux->nod ] );
                }
                else
                {
                    h[++dim_h] = aux->nod;
                    p[ h[dim_h] ] = dim_h;
                    bubble_up( dim_h );
                }
            }

            aux = aux->next;
        }
    }
}

void citeste()
{
    f >> N >> M;
    int x,y,z;
    while( f >> x >> y >> z )
        adauga_in_a( x ,y, z );
        adauga_in_a( y, x , z);
}

void adauga_in_a(int x , int y, int z )
{
    adi* nou =  new adi;
    nou->nod = y;
    nou->cost = z;
    nou->next = lista_a[x];
    lista_a[x] = nou;

}

void bubble_down( int index )
{
    int fiu = index;
    while( index <= dim_h )
    {
        if( (index*2) <= dim_h )
        {
            fiu = index*2;
            if( fiu + 1 <= dim_h)
                if( d[fiu] > d[fiu + 1 ])
                    fiu++;
        }
        else return;

        if ( d[ fiu ] < d[ index ] )
        {
            p[ h[fiu ] ] = index;
            p[ h[index] ] = fiu;

            schimba( fiu , index );
            index = fiu;
        }
        else return;
    }
}

void bubble_up( int index )
{
    int tata;
    while( 1 )
    {
        tata = index/2;
        if ( tata <= 1 )
        {
            if( d[tata] > d[index ] )
            {
                p[ h[tata] ] = index;
                p[ h[index] ] = tata;
                schimba( tata, index );
                index = tata;
            }
            else return;
        }

        else return;
    }
}