#include<fstream>
#include<algorithm>
using namespace std;
int n, m, i, nr, r1, r2, sum;
pair<int, int> sol[400002];
int v[200002];
struct muchie{
    int cost;
    int x;
    int y;
};
muchie w[400002];
int cmp(const muchie &a, const muchie &b){
    return a.cost < b.cost;
}
int rad(int x){
    int r = x;
    while(v[r] > 0){
        r = v[r];
    }
    x = r;
    while(v[r] > 0){
        int aux = v[r];
        v[r] = x;
        r = aux;
    }
    return x;
}
ifstream fin("apm.in");
ofstream fout("apm.out");
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> w[i].x >> w[i].y >> w[i].cost;
    }
    sort(w + 1, w + m + 1, cmp);
    for(i  = 1; i <= n; i++){
        v[i] = -1;
    }
    for(i = 1; i <= m; i++){
        r1 = rad(w[i].x);
        r2 = rad(w[i].y);
        if(r1 != r2){
            sum += w[i].cost;
            nr++;
            sol[nr].first = w[i].x;
            sol[nr].second = w[i].y;
            if(v[r1] < v[r2]){
                v[r1] += v[r2];
                v[r2] = r1;
            }
            else{
                v[r2] += v[r1];
                v[r1] = r2;
            }
        }
    }
    fout<< sum <<"\n"<< nr <<"\n";
    for(i = 1; i <= nr; i++){
        fout<< sol[i].first <<" "<< sol[i].second <<"\n";
    }
    return 0;
}