//Algorimul lui Kruskal pentru determinarea
//arborelui de cost minim 50 de puncte pe infoarena
//timp depasit
#include<cstdio>
#define Nmax 200001
#define Mmax 400001

int n,m,componenta[Nmax],k; //componenta va retine componenta conexa din care
long suma;                //face parte nodul i

struct muchie              //numarul de muchii ale arborelui
  {unsigned int x,y;
   int cost;
  };
muchie a[Mmax];   //a = lista muchiilor grafului neorintat conex

struct muchie_fara_cost
  {unsigned int x,y;
  };
muchie_fara_cost L[Mmax];                          //L = lista muchiilor arborelui partial de cost minim

void citire()
{freopen("apm.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
  {scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].cost);
   componenta[i]=i;
  }
}

void det_arbore_de_cost_minim()
{int i,v1,v2,j;
for(i=1;i<=m && k<n-1;i++)
   if(componenta[a[i].x]!=componenta[a[i].y])
     {k++;
      L[k].x=a[i].x;
      L[k].y=a[i].y;
      suma=suma+a[i].cost;
      if(componenta[a[i].x]>componenta[a[i].y])
          {v1=componenta[a[i].y]; //valoarea cu care trebuie inlocuit v2
           v2=componenta[a[i].x];
          }
        else
           {v1=componenta[a[i].x];
            v2=componenta[a[i].y];
           }
      for(j=1;j<=n;j++)
        if(componenta[j]==v2)
          componenta[j]=v1;
     }
}

void ordonare()
{int i,j;
muchie aux;
for(i=1;i<m;i++)
  for(j=i+1;j<=m;j++)
    if(a[i].cost>a[j].cost)
       {aux=a[i];
       a[i]=a[j];
       a[j]=aux;
       }
}

void afisare()
{freopen("apm.out","w",stdout);
printf("%ld\n%d\n",suma,k);
for(int i=1;i<=k;i++)
  printf("%d %d\n",L[i].x,L[i].y);
}

int main()
{citire();
ordonare();
det_arbore_de_cost_minim();
afisare();
return 0;
}