#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int nrNoduri;
#define maxNrMuchii 400000
int tata[maxNrMuchii];
//int *tata;
//int corect[M];
int *corect;
//struct Muchie{int nod1,nod2,cost;} muchie[M];
struct Muchie{int nod1,nod2,cost;} *muchie;

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 (){
	//citire
    int nrMuchii;
	in>>nrNoduri>>nrMuchii;
	//tata=new int[nrMuchii+1];
	corect=new int[nrNoduri];
	muchie=new Muchie[nrMuchii+1];
    for (register int i=1;i<=nrMuchii;i++)
		in>>muchie[i].nod1>>muchie[i].nod2>>muchie[i].cost;
	//prim
    sort (muchie+1,muchie+1+nrMuchii,cmp);
    int k=0,suma=0;
    for (register int i=1;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-1;i++)
		out<<muchie[corect[i]].nod1<<" "<<muchie[corect[i]].nod2<<"\n";
}
int main(){
citire();
return 0;
}