#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;

void coboara(long pos){
    long lson = 2*pos;
    long rson = 2*pos+1;

    long ales = lson;

    if(lson <= m){
        if(rson <=m && vec[rson].cost < vec[lson].cost){
            ales = rson;
        }

        if(vec[ales].cost < vec[pos].cost){
            swap(vec[ales], vec[pos]);
            coboara(ales);
        }
    }
}

void urca(long pos){
    long father = pos/2;
    if(father){
        if(vec[father].cost > vec[pos].cost){
            swap(vec[father], vec[pos]);
            urca(father);
        }
    }
}
void sterge(long pos){
    swap(vec[pos],vec[m]);
    m--;
    coboara(pos);
}

void construieste(){
   for(long i=m/2; i>0; i--)
        coboara(i);
}

//----HEAPURI--///
int main(){

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

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

    construieste();

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

    long cost_final = 0;
    bool continua = false;

    while(!continua && m){
        if(padure[vec[1].x]!= padure[vec[1].y]){
            long radacina =  padure[vec[1].y];
            continua = true;
            for(long i=1; i<=n; i++){
                if(padure[i] == radacina)
                    padure[i] = padure[vec[1].x];
                else if(padure[i]!=radacina && padure[i]!=padure[vec[1].x])
                    continua = false;
            }
            cost_final += vec[1].cost;
            final.push_back(vec[1].x), final.push_back(vec[1].y);
        }
        sterge(1);
    }

    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;
}