#include <iostream>
#include <fstream>

using namespace std;

struct muchie{
    int i;
    int j;
    int cost;
};

int main(){
    ifstream f("apm.in");
    ofstream of("apm.out");
    int n,m;
    f >> n >> m;
    muchie mu[m+1];
    //cout << "M " << m << endl;
    for(int i = 1;i<=m;i++){
        f >> mu[i].i >> mu[i].j >> mu[i].cost;
    }
    muchie aux;
    for(int i = 1;i<=m-1;i++){
        for(int j = i+1;j<=m;j++){
            if(mu[i].cost > mu[j].cost){
                aux = mu[i];
                mu[i] = mu[j];
                mu[j] = aux;
            }
        }
    }
    int s = 0;
    int arb[n+1];
    muchie sol[m+1];
    int sol_n = 0;
    for(int i = 1;i<=n;i++){
        arb[i] = i;
    }
    for(int i = 1;i<=m;i++){
        if(arb[mu[i].i] != arb[mu[i].j]){
            s = s + mu[i].cost;
            sol_n++;
            sol[sol_n] = mu[i];
            int ai = arb[mu[i].i];
            int aj = arb[mu[i].j];
            for(int j = 1;j<=n;j++){
                if(arb[j] == aj){
                    arb[j] = ai;
                }
            }
        }
    }
    of << s << endl << sol_n << endl;
    for(int i = 1;i<=sol_n;i++){
        of << sol[i].i << " " << sol[i].j << endl;
    }
}