#include <fstream>
#include <algorithm>

using namespace std;

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

const int Nmax = 200005;
const int Mmax = 400005;

struct muchie{
    int nod1, nod2, cost;
};

struct padure{
    int root, depth;
};

int n, m, poz, cost_total;
muchie edges[Mmax], sol[Nmax];
padure disjoint[Nmax];

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

int find_Root(int nod){
    if(disjoint[nod].root == -1){
        return nod;
    }

    int root = find_Root(disjoint[nod].root);
    disjoint[nod].root = root;
    return root;
}

void Union(int x, int y){
    int r_x, r_y;

    r_x = find_Root(x);
    r_y = find_Root(y);

    if(r_x == r_y){
        return;
    }

    if(disjoint[r_x].depth > disjoint[r_y].depth){
        swap(r_x, r_y);
    }

    disjoint[r_y].depth += disjoint[r_x].depth;
    disjoint[r_x].root = r_y;
}

bool isValid(int nod1, int nod2){
    return (find_Root(nod1) != find_Root(nod2));
}

void citire(){
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> edges[i].nod1 >> edges[i].nod2 >> edges[i].cost;
    }
}

void preinit_dsu(){
    for(int i = 1; i <= n; i++){
        disjoint[i].depth = 1;
        disjoint[i].root = -1;
    }
}

void calcul_apm(){
    sort(edges + 1, edges + m + 1, cmp);

    poz = 0;
    cost_total = 0;
    for(int i = 1; i <= m; i++){
        if(isValid(edges[i].nod1, edges[i].nod2)){
            poz++;
            sol[poz] = edges[i];
            cost_total += edges[i].cost;

            Union(edges[i].nod1, edges[i].nod2);
        }
    }
}

void afisare(){
    fout << cost_total << '\n' << poz << '\n';
    for(int i = 1; i <= poz; i++){
        fout << sol[i].nod1 << " " << sol[i].nod2 << '\n';
    }
}

int main(){
    citire();

    preinit_dsu();
    calcul_apm();

    afisare();

    return 0;
}