#include <vector>
#include <stdio.h>
using namespace std;
#define nmax 200001
#define mmax 400001
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");
int t[nmax],n,m,C;
vector<int> v;
typedef struct {
	int c,x,y;
} muchie;
muchie M[mmax],aux[mmax];
void swap(muchie &x,muchie &y)
 {
 muchie ax=x;
 x=y;
 y=ax;
 }
void read()
 {
 fscanf(f,"%d %d",&n,&m);
 for(int i=1;i<=m;i++)
  fscanf(f,"%d %d %d",&M[i].x,&M[i].y,&M[i].c);
 }
void interc(int l,int mij,int r)
 {
 int i,j,k;
 k=l-1;
 i=l;
 j=mij+1;
 while(i<=mij&&j<=r)
  {
  if(M[i].c<M[j].c)
   {
   aux[++k]=M[i];
   i++;
   }
  else
   {
   aux[++k]=M[j];
   j++;
   }
  }
 while(i<=mij)
  aux[++k]=M[i++];
 while(j<=r)
  aux[++k]=M[j++];
 for(i=l;i<=r;i++)
  M[i]=aux[i];
 }
void msort(int l,int r)
 {
 int mij=(l+r)/2;
 if(l==r) return;
 msort(l,mij);
 msort(mij+1,r);
 interc(l,mij,r);
 }
void reunite(int i,int j)
 {
 i=t[i];
 j=t[j];
 for(int k=1;k<=n;k++)
  if(t[k]==i)
   t[k]=j;
 }
void solve()
 {
 msort(1,m);
 int i,x,y,c;
 for(i=1;i<=n;i++)
  t[i]=i;
 for(i=1;i<=m;i++)
  {
  x=M[i].x;
  y=M[i].y;
  c=M[i].c;
  if(t[x]==t[y]) continue;
  reunite(x,y);
  v.push_back(x);
  v.push_back(y);
  C+=c;
  }
 }
void print()
 {
 fprintf(g,"%d\n",C);
 fprintf(g,"%d\n",((v.size()+1)/2));
 for(unsigned i=0;i<v.size();i+=2)
  {
  fprintf(g,"%d %d\n",v[i],v[i+1]);
  //g<<v[i]<<" "<<v[i+1]<<endl;
  }
 }
int main()
 {
 read();
 solve();
 print();
 return 0;
 }