//algoritmul Kruskal
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
//#define maxNrMuchii 400000

int nrNoduri,nrMuchii;
struct Muchie{int nod1,nod2,cost;} *muchie;
int *tata;

int radacina(int& nod){
    return tata[nod] ? tata[nod]=radacina(tata[nod]) : nod;
}
void unire(int& nod1,int& nod2){
    tata[radacina(nod1)]=radacina(nod2);
}
bool gasire(int& nod1,int& nod2){
    return radacina(nod1)==radacina(nod2);
}
bool cmp(const Muchie& a,const Muchie& b){
    return a.cost<b.cost;
}
void citire (){
	in>>nrNoduri>>nrMuchii;
	muchie=new Muchie[nrMuchii+1];
    for (register int i=1;i<=nrMuchii;i++)
		in>>muchie[i].nod1>>muchie[i].nod2>>muchie[i].cost;
}
void Kruskal(){
    sort (muchie+1,muchie+1+nrMuchii,cmp);
	tata=new int[nrNoduri+1];
	for(int i=1;i<=nrNoduri;++i)
		tata[i]=0;
	int suma=0,corect[nrNoduri];
    for (register int i=1,k=0;i<=nrMuchii;i++){
        if (!gasire (muchie[i].nod1,muchie[i].nod2)){
            suma+=muchie[i].cost;
            unire(muchie[i].nod1,muchie[i].nod2);
            corect[++k]=i;
        }
    }
    //afisare
	out<<suma<<"\n";
	out<<nrNoduri-1<<"\n";
	for (register int i=1;i<nrNoduri;i++)
		out<<muchie[corect[i]].nod1<<" "<<muchie[corect[i]].nod2<<"\n";
}
int main(){
citire();
Kruskal();
return 0;
}