#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

struct muchie
{
    int nod_1 , nod_2 , cost ;
}v[400001];
int c[400001];
muchie sol[200001];
int n , m , k , minim , maxim , costTotal;

bool criteriu ( muchie v1 , muchie v2 )
{
    return v1.cost < v2.cost;
}
int main()
{
    f >> n >> m ;
    for ( int i = 1; i <= m ; i++ )
        f >> v[i].nod_1 >> v[i].nod_2 >> v[i].cost ;
    sort ( v+1 , v+m+1 , criteriu) ;
    for ( int i = 1; i <= n ; i++ ) c[i] = i;
    for ( int i = 1; i <= m ; i++ )
    {
        int n1 = v[i].nod_1;
        int n2 = v[i].nod_2;
        if ( c[n1] !=  c[n2] )
        {
            sol[++k] = v[i];
            costTotal += v[i].cost;
            if ( c[n1] < c[n2] ) minim = c[n1] , maxim = c[n2];
            else minim = c[n1] , maxim = c[n2];
            for ( int j = 1; j <= n; j++ )
                if ( c[j] == maxim ) c[j] = minim;
        }
    }
    g << costTotal << "\n" ;
    g << k << "\n" ;
    for ( int i = 1 ; i <= k; i++ )
        g << sol[i].nod_1 << " " << sol[i].nod_2 << "\n" ;

    return 0;
}