#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,s,nrniv[200001],tata[200001],nralese,nrmuchii;
struct muchie{
         int x,y,c;

    }muchii[400001],rez[200001];
int gaseste(int x){
 if(tata[x]!=0)
          return gaseste(tata[x]);
    else return x;

}
bool cmp(muchie a, muchie b){
return a.c<b.c;

}

void uneste(int r1,int r2){
if(nrniv[r1]>nrniv[r2])tata[r2]=r1;
else{
    if(nrniv[r1]<nrniv[r2])tata[r1]=r2;
    else{
        tata[r1]=r2;
        nrniv[r2]++;

    }

}
}

int main()
{
    fin >> n >>m;
     for(int i=1;i<=m;i++)
      fin >> muchii[i].x>> muchii[i].y>> muchii[i].c;

      sort(muchii+1,muchii+m+1,cmp);




      for(int i=1;i<=m && nralese<n-1;i++){
           int r1 = gaseste(muchii[i].x);
           int r2 = gaseste(muchii[i].y);

           if(r2!=r1){
            nralese++;
            s+=muchii[i].c;
            rez[nralese]=muchii[i];

            nrmuchii++;
           uneste(r1,r2);

           }

      }

   fout << s<< endl;
   fout << nrmuchii<< endl;
   for(int i=1;i<=nrmuchii;i++)
       fout<< rez[i].y<<" "<< rez[i].x<<endl;

    return 0;
}