# include <stdio.h>      
# define nmax 200001
# define mmax 400001
struct muchie{
    int x,y,ct;
}G[mmax],S[mmax];
int N,M,C[nmax],X[nmax],Y[nmax];
long CT;
void sort(int st,int dr)
{
  int i=st,j=dr;
  muchie p=G[(st+dr)>>1];
  if (dr<=st) return;
  while (i<=j){
    while (G[i].ct<p.ct) i++;
    while (p.ct<G[j].ct) j--;
    if (i<=j) {
    G[0]=G[i];G[i]=G[j]; G[j]=G[0];
    i++; j--;
    }
  }
  if (st<j) sort(st,j);
  if (i<dr) sort(i,dr);}
int main(){
  int i,a,k=0,j;
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  scanf("%d %d",&N,&M);
  for (i=1;i<=M;++i)
    scanf("%d %d %d",&G[i].x,&G[i].y,&G[i].ct);
  sort(1,M);
  for (i=1;i<=N;++i) C[i]=i;
  i=1;
  while (k<N-1){
    if (C[G[i].x]!=C[G[i].y]){
    k++;
    CT+=G[i].ct; X[k]=G[i].x;Y[k]=G[i].y;
    a=C[G[i].x];
    for (j=1;j<=k;++j){
	 if (C[X[j]]==a) C[X[j]]=C[G[i].y];
	 if (C[Y[j]]==a) C[Y[j]]=C[G[i].y];
	}
      }
     ++i;
   }      
  printf("%ld\n",CT);      
  printf("%d\n",N-1);      
  for (i=1;i<=k;++i)      
     printf("%d %d\n",X[i],Y[i]);      
  return 0;      
}