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

#define VMAX 200005

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int V, E, tata[VMAX], cost_final;
struct muchie{
    int u, v, cost;
};
vector<muchie> edges, apm;

bool cmp(muchie a, muchie b){
    return a.cost < b.cost;
}

int find(int t){
    if(t == tata[t])
        return t;
    return tata[t] = find(tata[t]);
}

int main(){
    f >> V >> E;
    for(int i = 1; i <= E; i++){
        int x, y, z;
        f >> x >> y >> z;
        edges.push_back({x, y, z});
    }
    for(int i = 1; i <= V; i++)
        tata[i] = i;

    sort(edges.begin(), edges.end(), cmp);

    for(auto& m : edges){
        int ru = find(m.u), rv = find(m.v);

        if(ru != rv){
            tata[ru] = rv;
            apm.push_back(m);
            cost_final += m.cost;
        }

        if(apm.size() == V - 1)
            break;
    }

    g << cost_final << '\n' << V - 1 << '\n';
    for(auto& x : apm)
        g << x.u << ' ' << x.v << '\n';
    return 0;
}