#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{
 int i,j,cost;
};
int n,m,nr;
bool cmp(const muchie &a,const muchie &b){
 return a.cost<b.cost;
}
muchie M[400001];
int cc[200001],nrm[200000];
int con(int i){
 if(cc[i]==i)return i;
  cc[i]=con(cc[i]);
  return cc[i];
}
int Kruskal(){
 int k=0,x,y,cost_apm=0;
 sort(M+1,M+m+1,cmp);
 for(int i=1;i<=n;i++)
  cc[i]=i;
  n--;
  while(nr<n){
  k++;
  x=con(M[k].i);
  y=con(M[k].j);
  if(x!=y){
    cost_apm+=M[k].cost;
    cc[x]=y;
    nrm[++nr]=k;
   }
 }
 return cost_apm;
}
void afisare(){
g<<Kruskal()<<'\n'<<n-1<<'\n';
for(int i=1;i<=n;i++)
g<<M[nrm[i]].i<<' '<<M[nrm[i]].j<<'\n';
};
void citire(){
 f>>n>>m;
 for(int i=1;i<=m;i++)
  f>>M[i].i>>M[i].j>>M[i].cost;
}
int main(){
 citire();
 afisare();
}