#include<iostream>
#include<fstream>
#include<cstring>
#define nmax 200002
#define mmax 400004
using namespace std;
ifstream f("apm.in",fstream::in);
ofstream g("apm.out",fstream::out);
typedef struct
{int  inc,sf,cost;}muchie;
muchie M[mmax];
muchie sol[nmax];
int nrsol;
int L[nmax];
long SUM;
int  n,m;
void read()
{int  i;
 f>>n>>m;
  for(i=1;i<=m;i++)
	  f>>M[i].inc>>M[i].sf>>M[i].cost;
}
void init()
{int i;
 for(i=1;i<=n;i++)
	 L[i]=i;
}
void show_muchii()
{unsigned short int i;
 for(i=1;i<=m;i++)
	 cout<<"["<<M[i].inc<<","<<M[i].sf<<","<<M[i].cost<<"] ";
     cout<<"\n";
}
void schimbint(int  &a,int  &b)
{int  aux;
 aux=a;
 a=b;
 b=aux;
}
void schimbmuchie(muchie &a,muchie &b)
{muchie aux;
 aux=a;
 a=b;
 b=aux;
}
void divizeaza(int  s,int  d,int  &m)
{int  i=s,j=d,pi=0,pj=1;
 while(i<j)
 {if(M[i].cost>M[j].cost)
	  schimbint(pi,pj),schimbmuchie(M[i],M[j]);
  i+=pi;
  j-=pj;
 }
 m=i;
}
void qs(int  s,int  d)
{int  m;
 if(s<d)
 {divizeaza(s,d,m);
  qs(s,m-1);
  qs(m+1,d);
 }
}
void Kruskal()
{int k,i,xx,yy,j;
 k=i=1;
 while(k<n)
 {if(L[M[i].inc]!=L[M[i].sf])
 {k++;
  sol[++nrsol]=M[i];
  SUM+=M[i].cost;
  xx=L[M[i].sf];
  yy=L[M[i].inc];
  for(j=1;j<=m;j++)
	if(L[j]==xx)
		L[j]=yy;
 }
 i++;
 }
}
void show_L()
{int i;
 for(i=1;i<=n;i++)
	 cout<<L[i]<<" ";
cout<<"\n\n";
}
void show_solutii()
{int i;
 g<<SUM<<"\n";
 g<<nrsol<<"\n";
 for(i=1;i<=nrsol;i++)
	 g<<sol[i].inc<<" "<<sol[i].sf<<"\n";
}
int main()
{read();
 init();
 //show_muchii();
 qs(1,m);
 //show_muchii();
 Kruskal();
 show_solutii();
 f.close();
 g.close();
 return 0;
}