#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
#define MAX_N 200000
#define MAX_M 400000
struct muchie{
    long x, y, cost;
};

long n, m, padure[MAX_N];
muchie vec[MAX_M];
vector<long> final;


//-----===========QUICK SORT =========--------//
int position(int li, int ls){
    short int mod =1;
    while(li < ls){
        if(vec[li].cost > vec[ls].cost){
            swap(vec[li], vec[ls]);
            mod *=(-1);
        }

        if(mod == 1) li++;
        else ls--;
    }

    return li;
}


void quick(int li, int ls){
    if(li< ls){
        int lm  = position(li,ls);
        quick(li, lm-1);
        quick(lm+1, ls);
    }
}
//-------QUICK_SORT------------////

long grup(long x){
    if(padure[x] == x){
        return x;
    }else{
        padure[x] = grup(padure[x]);
        return padure[x];
    }
}

void unire(long x, long y){
    padure[grup(x)] = grup(y);
}
int main(){

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

    for(long i=0; i<m; i++){
        fin >> vec[i].x, fin >> vec[i].y, fin >> vec[i].cost;
    }


    quick(0,m-1); // sortez vectorul vec dupa costul muchiei

    /// formez padure
    for(long i=1; i<=n; i++){
        padure[i] = i;
    }

    long cost_final = 0;
   for(long i=0; i<m; i++){
        if(grup(padure[vec[i].x])!= grup(padure[vec[i].y])){
            unire(vec[i].x, vec[i].y);
            cost_final += vec[i].cost;
            final.push_back(vec[i].x), final.push_back(vec[i].y);
        }
   }

    fout << cost_final << '\n';
    fout << final.size()/2 << '\n';

    for(size_t i=0; i<final.size(); i+=2){
        fout << final[i] << " "<<final[i+1]<<'\n';
    }


return 0;
}