#include <cstdio>
#include <algorithm>

using namespace std;

#define IN "apm.in"
#define OUT "apm.out"

int n , m;
int T[200002];

int Find_Root(int x)
{
    int aux , a;

    aux = x;
    while (T[aux]!=aux)
        aux = T[aux];

    while (T[x]!=x){
        a = T[x];
        T[x] = aux;
        x = a;
    }

 return aux;

}

struct element
{
    int x , y , c;
}v[400002];

struct alt_element
{
    int x , y;
}sol[400002];

bool comp ( element a , element b )
{
    if ( a.c > b.c )
        return 0;
    return 1;
}

void Read()
{
    int nod1 , nod2 , cost , i;

    scanf ( "%d%d" , &n , &m );

    for ( i = 1 ; i <= m ; i ++ )
    {
        scanf ( "%d%d%d" , &nod1 , &nod2 , &cost );
        v[i].x = nod1 , v[i].y = nod2 , v[i].c = cost;
        T[nod1] = nod1 , T[nod2] = nod2;
    }

}

void Solve()
{
    int i , sum , r1 , r2 , k = 0;

    sort ( v + 1 , v + m + 1 , comp );
    sum = 0;

    for ( i = 1 ; i <= m ; i ++ ){
        r1 = Find_Root(v[i].x) , r2 = Find_Root(v[i].y);
        if ( r1 != r2 )
            T[r1] = r2 , sum += v[i].c , sol[++k].x = v[i].x , sol[k].y = v[i].y;

    }

    printf ( "%d\n%d\n" , sum , n-1 );

    for ( i = 1 ; i <= k ; i ++ )
        printf ( "%d %d\n" , sol[i].x , sol[i].y );


}

int main()
{
    freopen ( IN , "r" , stdin );
    freopen ( OUT , "w" , stdout );

    Read();
    Solve();
}