#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
#define nmax 200010
#define INF 1001
struct triplet{
   int a,b,c;
};
vector<triplet> listam;
int TATA[nmax],RANK[nmax];

void qs(int li,int ls){
     int i=li,j=ls;
     int pivot=listam[(li+ls)/2].c;
     while(i<j){
       while(listam[i].c<pivot)i++;
       while(listam[j].c>pivot)j--;
       if(i<=j){swap(listam[i],listam[j]);i++;j--;}
     }
     if(li<j)qs(li,j);
     if(ls>i)qs(i,ls);
}

int radacina(int nod){
   int rad,aux;
   for(rad=nod;rad!=TATA[rad];rad=TATA[rad]);
   //fac compresia drumurilor
   for(;nod!=TATA[nod];){
       aux=TATA[nod];
       TATA[nod]=rad;
       nod=aux;
   }
   return rad;
}

void reuniune(int a,int b){
   if(RANK[a]>RANK[b]){
      TATA[b]=a;
   }else TATA[a]=b;
   if(RANK[a]==RANK[b])RANK[b]++;
}



int main(){
   ifstream fin("apm.in");
   ofstream fout("apm.out");
   int n,m;
   int a,b,c;
   int i;
   fin>>n>>m;
   triplet aux;
   for(i=1;i<=n;i++){TATA[i]=i;RANK[i]=1;}
   for(i=0;i<m;i++){
     fin>>aux.a>>aux.b>>aux.c;
     listam.push_back(aux);
   }
   qs(0,m-1);//sortez crescator dupa cost muchiile
   //for(i=0;i<m;i++)cout<<listam[i].c<<endl;
   int ind=0;
   long long cost=0;
   for(i=1;i<n;i++){//trebuie sa aleg n-1 muchii care nu inchid cicluri
      while(radacina(listam[ind].a)==radacina(listam[ind].b))ind++;
      //iau muchia ind
      cost+=listam[ind].c;
      //cout<<listam[ind].c<<endl;
      listam[ind].c=INF;
      //acum  ii setez costul de INF, ca sa stiu ca am luat-o
      //arat ca cele doua noduri sunt acum in aceeasi componenta
      reuniune(radacina(listam[ind].a),radacina(listam[ind].b));
      ind++;
   }
   fout<<cost<<"\n"<<n-1<<"\n";
   for(ind=1,i=0;ind<n;i++){
     if(listam[i].c==INF){fout<<listam[i].a<<" "<<listam[i].b<<"\n";ind++;}
   }
   
return 0;
}