#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, arbore[200008], cost_minim, muchii, k, sol[200008] ;

struct muchie
{
    int x;
    int y;
    int cost;
} a[400008] ;


void citire();
void init();
void Kruskal();
void afisare();

bool comp ( muchie a , muchie b )
{
    return a.cost < b.cost ;
}


int main()
{
    citire();
    sort( a + 1 , a + 1 + m , comp ) ;
    init();
    Kruskal();
    afisare();
    return 0 ;
}

void citire()
{
    int i ;
    fin >> n >> m ;
    for ( i = 1 ; i <= m; i++ )
        fin >> a[i].x >> a[i].y >> a[i].cost ;
}

void init()
{
    int i ;
    for ( i = 1  ; i <= n  ; i++) arbore[i] = i ;
}

void Kruskal()
{
    int i = 1, j ;
    while ( muchii < n - 1 )
    {
        if ( arbore[a[i].x] != arbore[a[i].y])
        {

            muchii++; sol[muchii] = i ;
            cost_minim+= a[i].cost ;
            k = arbore[a[i].x] ;
            for ( j = 1 ; j <= n ; j++ )
                if ( arbore[j] == k ) arbore[j] = arbore[a[i].y] ;

        }
        i++;

    }
}

void afisare()
{
    int i ;
    fout << cost_minim << '\n' ;
    fout << n-1 << '\n' ;
    for ( i = 1 ; i <= n-1 ; i++ ) fout << a[sol[i]].x << " " << a[sol[i]].y << '\n' ;
}