#include <fstream>
#include <vector>
#include <iostream>
#define nmax 200010
using namespace std;
#define INF 200000200

vector <pair<int,int> > graf[nmax],VRASP;
int poz[nmax],vec[nmax],cost_min[nmax];
int heap[nmax];
int N=0;//dimensiunea heapului

void urca(int loc){
   int x;
   int aux;
   while((x=loc/2) && cost_min[heap[loc]]<cost_min[heap[x]]){
      //interschimb nodul de pe locul loc cu tatal sau
      swap(heap[x],heap[loc]);
      swap(poz[heap[x]],poz[heap[loc]]);
      loc=x;
   }
}

void coboara(int loc){
   //cobor in fiul cel mai mic dintre cei doi
    int aux, x, y = 0;
    while (loc != y){
	y = loc;
	if ((x=y*2)<=N && cost_min[heap[loc]]>cost_min[heap[x]]) loc = x;
        x++;
	if (x<=N && cost_min[heap[loc]]>cost_min[heap[x]]) loc = x;
          swap(heap[loc],heap[y]);
          swap(poz[heap[loc]],poz[heap[y]]);
	}
}


void adauga_la_apm(int x){
     int nod;
     int cost;
     for(vector<pair<int,int> >::iterator it=graf[x].begin();it<graf[x].end();it++){
          nod=(*it).first;
          cost=(*it).second;
          if(cost<cost_min[nod]){//verific daca e mai bine sa reactualizez costul acestui nod
              cost_min[nod]=cost;
              vec[nod]=x;
          }
     }
}

int main(){
   int n,m;
   ifstream fin("apm.in");
   ofstream fout("apm.out");
   fin>>n>>m;
   int x,y,c;
   int i;
   for(i=0;i<m;i++){
     fin>>x>>y>>c;
     graf[x].push_back(make_pair(y,c));
     graf[y].push_back(make_pair(x,c));
   }
   //aleg un nod arbitrar, sa zicem 1
       for(i=1;i<=n;i++){
          cost_min[i]=INF;
       }
       cost_min[1]=0;//ca sa ma asigur ca apare in varful heap-ului
       poz[1]=0;
       //il adaug la apm, adica ii reactualizez vecinii, acum ei sunt posibile noduri catre care sa ma extind cu diverse costuri spre fiecare       
       adauga_la_apm(1);
       for(i=2;i<=n;i++){
         //inserez in heap nodul i
         heap[++N]=i;
         poz[i]=N;
         urca(N);
       }
   int nod;
   //la fiecare pas scot din heap minimul=>am un nod; il adaug la apm
   long long suma=0; 
   for(i=1;i<n;i++){//mai am de ales n-1 noduri
      //scot varful din heap
      x=heap[1];
      //cout<<"am scos din heap "<<x<<", N="<<N<<endl;
      heap[1]=heap[N];
      poz[heap[1]]=1;
      N--;        
      coboara(1);
      poz[x]=0;
      adauga_la_apm(x);
      VRASP.push_back(make_pair(x,vec[x]));
      suma+=cost_min[x];
      //cout<<"am adaugat muchia de cost "<<cost_min[x]<<" adica muchia "<<x<<" "<<vec[x]<<endl;
      //in heap trebuie sa modific locul tuturor vecinilor nodului curent adaugat la apm, pt ca cost_min[vecin] se modifica...
      //cout<<x<<" are vecinii: "<<endl;
      for(vector<pair<int,int> >::iterator it=graf[x].begin();it<graf[x].end();it++){
          if(poz[(*it).first]){urca(poz[(*it).first]);          /*cout<<(*it).first<<" ";*/}

      }//cout<<endl;
   }
   fout<<suma<<'\n';n--;
   fout<<n<<'\n';
   for(i=0;i<n;i++){
      fout<<VRASP[i].first<<" "<<VRASP[i].second<<'\n';
   }
return 0;
}