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


//--------=========Heap Sort =======---------
void Combinare(long vf,long m){ // formeaza un Minheap dintr-un varf si doua MinHeapuri
	long baza= 2*vf, valoare = vec[vf].cost, gata = 0;
	while(baza <=m && !gata){
		if(baza <m && vec[baza].cost < vec[baza+1].cost) baza++;
		if(valoare<vec[baza].cost){
			swap(vec[vf],vec[baza]); vf= baza; baza*=2;
		}else gata =1;
	}
}


void Heap(){ ///organizeaza vectorul ca minheap
	long i;
	for(i=m/2; i>=1; i--) Combinare(i,m);
}

void HeapSort(){
	
	Heap();
	for(long i=m; i>=2; i--){
		swap(vec[i],vec[1]);
		Combinare(1, i-1);
	}
}

//------------Heap Sort -----------///
int main(){
 
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >> n >> m;
     
    for(long i=1; i<=m; i++){
        fin >> vec[i].x, fin >> vec[i].y, fin >> vec[i].cost;
    }
	
	HeapSort();// sortez crescator vectorul vec dupa costuri 
	
    /// formez padure
    for(long i=1; i<=n; i++){
        padure[i] = i;
    }
 
    long cost_final = 0;
    bool continua = false;
    long index = 0;
    while(!continua && index !=m-1){
        index ++;
        if(padure[vec[index].x]!= padure[vec[index].y]){
            long radacina =  padure[vec[index].y];
            continua = true;
            for(long i=1; i<=n; i++){
                if(padure[i] == radacina)
                    padure[i] = padure[vec[index].x];
                else if(padure[i]!=radacina && padure[i]!=padure[vec[index].x])
                    continua = false;
            }
            cost_final += vec[index].cost;
            final.push_back(vec[index].x), final.push_back(vec[index].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;
}