#include <iostream>
#include <fstream>
#include <vector>
#include <utility>

using namespace std;
void quicksort( vector < vector < int > > &lista_muchii, int inf, int sup ){
    int i, j, x;
    vector < int > t;
    i = inf;
    j = sup;
    x = lista_muchii[(i+j)/2][2];
    do{
        while( i < sup && lista_muchii[i][2] < x ) i++;
        while( j > inf && lista_muchii[j][2] > x ) j--;
        if( i <= j ){
            t = lista_muchii[i];
            lista_muchii[i] = lista_muchii[j];
            lista_muchii[j] = t;
            i++;
            j--;
        }
    }while( i <= j );
    if( inf < j ) quicksort( lista_muchii, inf, j );
    if( i < sup ) quicksort( lista_muchii, i, sup );
}
int reprez( vector < int > &ind, int i ){
    if( ind[i] == i ) return i;
    ind[i] = reprez( ind, ind[i] );
    return ind[i];
}
void reuniune( vector < int > &ind, int i, int j ){
    ind[reprez(ind,i)] = reprez(ind,j);
}

int main(){
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n;
    int m;
    fin >> n >> m;
    vector < vector < int > > lista_muchii;
    vector <vector < int > > apm;
    for( int i = 0; i < m; i++ ){
        int x, y, c;
        fin >> x >> y >> c;
        vector < int > muchie;
        muchie.push_back(x);
        muchie.push_back(y);
        muchie.push_back(c);
        lista_muchii.push_back(muchie);
    }
    quicksort(lista_muchii,0,lista_muchii.size()-1);
    vector < int > ind;
    for( int i = 0; i <= n; i++ ){
        ind.push_back(i);
    }
    int nrmsel = 0;
    int suma = 0;
    for( int i = 0; i < m; i++ ){
        if( reprez(ind, lista_muchii[i][0]) != reprez(ind, lista_muchii[i][1]) ){
            apm.push_back(lista_muchii[i]);
            suma += lista_muchii[i][2];
            reuniune(ind, lista_muchii[i][0], lista_muchii[i][1]);
            nrmsel++;
            if(nrmsel == n - 1){
                break;
            }
        }
    }
    fout << suma << endl << apm.size() << "\n";
    for( int i = 0; i < apm.size(); i++ ){
        fout << apm[i][0] << " " << apm[i][1] << "\n";
    }
}