#include <bits/stdc++.h>

using namespace std;

struct kruskal{
    unsigned exInit;
    unsigned exFin;
    unsigned cost;
};

bool cmp(kruskal el, kruskal elDoi){
    return el.cost < elDoi.cost;
}

void showList(vector <kruskal> v){
    for(auto it: v)
        cout << endl << it.cost << " " << " " << it.exInit << " " << it.exFin;
}

vector <int> parinte(100);

int reprezentare(int nod){
    if(parinte[nod] == nod)
        return nod;
    else
        return reprezentare(parinte[nod]);
}

void reunire (int from, int to){
    int rootFrom = reprezentare(from);
    int rootTo   = reprezentare(to);
    if(rootFrom != rootTo)
        parinte[rootTo] = rootFrom;   
}

int main()
{
    ifstream fin("apm.in");
    unsigned noduri, muchii;
    
    fin >> noduri >> muchii;

    vector <kruskal> listaMuchii;
    unsigned copy = muchii;
    
    while(copy > 0){
        unsigned exInit;
        unsigned exFin;
        unsigned cost;

        fin >> exInit >> exFin >> cost;

        kruskal muchie;
        muchie.exInit = exInit;
        muchie.exFin  = exFin;
        muchie.cost   = cost;

        listaMuchii.push_back(muchie);
        
        copy --;
    }

    sort(listaMuchii.begin(),listaMuchii.end(), cmp);
    //showList(listaMuchii);
    
    for(int i = 1; i <= noduri; i++)
        parinte[i] = i;
    
    vector <kruskal> graf;
    unsigned nrMuSel = 0;
    unsigned suma    = 0;
    
    for(auto it: listaMuchii){
        unsigned from = it.exInit;
        unsigned to   = it.exFin;
        unsigned cost = it.cost;

        if(reprezentare(from) != reprezentare(to)){
            //cout << from << " " << to << endl;
            reunire(from, to);
            kruskal muchie;
            muchie.exInit = from;
            muchie.exFin  = to;
            muchie.cost   = cost;
            suma += cost;
            graf.push_back(muchie);
            nrMuSel += 1;
        }
    }

    ofstream fout("apm.out");
    fout << suma;
    fout << endl << nrMuSel << endl;

    for(auto it: graf){
        cout << it.exInit << " " << it.exFin << endl;   
        fout << it.exInit << " " << it.exFin << endl;
    }

    return 0;
}