#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int sef[200001];

struct pb{
    int nod1;
    int nod2;
    int cost;
};

bool comparaPret(pb &cost1, pb &cost2){
    return cost1.cost < cost2.cost;
}

int bigsef(int k){
    if(sef[k] == k)
        return k;
    else
        return sef[k]=bigsef(sef[k]);
}

void unire(int k, int p) {
    int rk = bigsef(k), rp = bigsef(p);
    if (rk != rp) {
        sef[rk] = rp;
    }
}

struct rasp{
    int nr1;
    int nr2;
};

vector<pb> lista;
vector<rasp> raspuns;

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        sef[i] = i;
    }
    int cost=0;
    int nodunu,noddoi,pret;
    for(int i=1;i<=m;i++){
        cin>>nodunu>>noddoi>>pret;
        struct pb info = {nodunu,noddoi,pret};
        lista.push_back(info);
    }
    sort(lista.begin(), lista.end(), comparaPret);
    int contor=1;
    for(int i=0;i<m;i++){
        if(sef[lista[i].nod1]!=sef[lista[i].nod2]&&contor!=n){
            unire(lista[i].nod1,lista[i].nod2);
            for(int j=1;j<=n;j++){
                sef[j] = bigsef(j);
            }
            cost += lista[i].cost;
            struct rasp rasptemp = {lista[i].nod1, lista[i].nod2};
            raspuns.push_back(rasptemp);
            contor++;
        }
    }
    cout<<cost<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++){
        cout<<raspuns[i].nr1<<" "<<raspuns[i].nr2<<"\n";
    }
}