#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
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;
queue<long>suba[MAX_N];

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--///

void grupare(long x, long y){
    while(!suba[y].empty()){
        long fr = suba[y].front();
        padure[fr] = padure[x];
        suba[x].push(fr);
        suba[y].pop();
    }
}
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;
        suba[i].push(i);
    }

    long cost_final = 0;
    long iteratii = m;
   for(long i=1; i<=iteratii; i++){
        if(padure[vec[1].x]!= padure[vec[1].y]){
            grupare(padure[vec[1].x], padure[vec[1].y]);
            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;
}