#include <fstream>
#include <algorithm>

using namespace std;

const int N = 100000, M = 200000;
int n, m, nr[N], t[N], cost, nrm;
bool muchie[M];

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

struct el{
    int x, y, c;
}
v[M];

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

}

void reuniune(int x, int y){
    int rx = radacina(x);
    int ry = radacina(y);
    if(nr[rx] < nr [ry]){
        t[rx] = ry;
        nr[ry] += nr[rx];
    }else{
        t[ry] = rx;
        nr[rx] += nr[ry];
    }

}

bool interogare(int x, int y){
    return (radacina(x) == radacina(y));
}

bool cmp(const el &a, const el &b){
    return a.c < b.c;
}

int main(){
    in >> n >> m;
    for(int i = 0; i < m; i++){

        in >> v[i].x >> v[i].y >> v[i].c;

    }
    sort(v, v + m, cmp);
    for(int i = 0; i < m; i++){
        if(!interogare(v[i].x, v[i].y)){
            reuniune(v[i].x, v[i].y);
            muchie[i] = true;
            nrm++;
            cost += v[i].c;
        }

    }
    out << cost << endl << nrm << endl;
    for(int i = 0; i < m; i++){
        if(muchie[i]){
            out << v[i].x << ' ' << v[i].y << endl;
        }
    }
    return 0;

}