#include <stdio.h>
#include <algorithm>
#define Nmax 200005
#define Mmax 400005
using namespace std;

int X[Mmax],Y[Mmax],C[Mmax],ind[Mmax],V[Mmax];
int TT[Nmax],Rg[Nmax];
int n,m,i,cmin,t1,t2;

int cmp(int x,int y){
	return C[x]<C[y];
}

int Find(int x){
	int r,y;
	for( r=x; r!=TT[r]; ) r=TT[r];

   while( x!=TT[x] ){
   	y=TT[x];
      TT[x]=r;
      x=y;
   }
   return r;
}
void Unite(int x,int y){
	if(Rg[x]>Rg[y]) TT[y]=x;
   else TT[x]=y;
   if(Rg[x] == Rg[y]) Rg[y]++;
}

int main(){
	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",&X[i],&Y[i],&C[i]),ind[i]=i;

   for(i=1;i<=n;++i) TT[i]=i, Rg[i]=1;
   sort(ind+1,ind+m+1,cmp);

   for(i=1;i<=m;++i){
   	t1=Find(X[ind[i]]),t2=Find(Y[ind[i]]);
      if( t1!=t2 ){
      	Unite(t1,t2);
         cmin+=C[ind[i]];
         V[++V[0]]=ind[i];
      }
   }

   printf("%d\n",cmin);
   printf("%d\n",V[0]);
   for(i=1;i<=V[0];++i)
   	printf("%d %d\n",X[V[i]],Y[V[i]]);

   fclose(stdin); fclose(stdout);
   return 0;
}