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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
    int u, v;
    int cost;
    bool operator< (const muchie& other) const{
        return cost < other.cost;
    }
};

vector<muchie> listaM;
vector<int> h;
vector<int> tata;

void initializari(int u){
    h[u] = 0;
    tata[u] = u;
}

int reprez(int u){
    if(tata[u] == u)
        return u;
    u = reprez(tata[u]);
    return u;
}

void reuneste(int u, int v){
    // presupunem ca nodurile u si v au reprezentanti diferiti
    int ru = reprez(u);
    int rv = reprez(v);
    if(h[ru] > h[rv])
        tata[rv] = ru;
    else{
        tata[ru] = rv;
        if(h[ru] == h[rv])
            h[rv] ++;
    }
}

int main(){
    int N, M;
    fin >> N >> M;
    listaM.reserve(M);
    h.assign(N+1, 0);
    tata.reserve(N+1);
    for(int i = 0; i < M; i++)
    {
        muchie a;
        fin >> a.u >> a.v >> a.cost;
        listaM.push_back(a);
    }
    sort(listaM.begin(), listaM.end());
    // trb sa gasesc apcm ul grafului
    // folosesc kruskal cu compresie de cale
    for(int i = 1; i <= N; i++){
        initializari(i);
    }
    int costAPM = 0;
    int contorM = 0;
    vector<muchie> apm;
    for(auto mch : listaM){
        int u = mch.u;
        int v = mch.v;
        if(reprez(u) != reprez(v)){
            reuneste(u, v);
            apm.push_back(mch);
            costAPM += mch.cost;
            contorM ++;
        }
        if(contorM == N-1)
            break;
    }
    fout << costAPM << endl;
    fout << apm.size() << endl;
    for(auto muchie : apm){
        fout << muchie.u << " " << muchie.v << endl;
    }
    return 0;
}