#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

#define N 200001

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

struct muchie{
    int x, y, c;
    muchie(int x, int y, int c):
        x(x), y(y), c(c) {}
};

int n, m, t[N], ctot, muchii;
vector<muchie> vm, sel;

bool cmp(muchie m1, muchie m2){
    return m1.c < m2.c;
}

int radacina(int x){
    if(t[x] == 0)
        return x;
    int k = radacina(t[x]);
    t[x] = k;
    return k;
}

void uneste(muchie m){
    int rx = radacina(m.x);
    int ry = radacina(m.y);

    if(rx != ry){
        t[ry] = rx;
        ctot += m.c;
        sel.push_back(m);
        muchii++;
    }
}

int main(){
    in >> n >> m;
    while(m--){
        int x, y, c;
        in >> x >> y >> c;
        vm.push_back(muchie(x,y,c));
    }

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

    for(muchie m : vm){
        uneste(m);
        if(muchii == n-1)
            break;
    }
    out << ctot << '\n' << n-1 << '\n';
    for(muchie m : sel)
        out << m.x << ' ' << m.y << '\n';
}