#include<stdio.h>
#include<vector>
#include<iostream>
using namespace std;

#define Nmax 200001

typedef struct muchie
{
	int x, y, cost;
}Tmuchie;

Tmuchie G[Nmax];

int ord[Nmax],pad[Nmax],arb[Nmax],cardinal[Nmax];
int n, m;

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

bool cmp(int i,int j)
{
	return (G[i].cost<G[j].cost);
}

void uneste(int x,int y)
{
  int i,multime1, multime2;
  multime1=pad[x];
  multime2=pad[y];
  
	
  if (cardinal[x]>cardinal[y])
	  {
	 for(i=1;i<=n;i++)
	if(pad[i]==multime2)
		pad[i]=multime1;
	
	  }
	  else{
		
	 for(i=1;i<=n;i++)
	if(pad[i]==multime1)
		pad[i]=multime2;
        }
		
 cardinal[x]=cardinal[y]=cardinal[x]+cardinal[y];		
}
  
	
int main()
{
	int i,suma=0,k=0;
	citire();
	
	for(i=1;i<=n;i++)
	   {
        pad[i]=i;
	    cardinal[i]=1;
       }
	sort(ord+1,ord+m+1,cmp);
	
	
	
	for(i=1;i<=m;i++)
	  if(pad[G[ord[i]].x]!=pad[G[ord[i]].y])
		{
			suma=suma+G[ord[i]].cost;
        	uneste(G[ord[i]].x,G[ord[i]].y);
			arb[++k]=ord[i];
	    }
	  
	  
freopen("apm.out","w",stdout);
	 printf("%d\n",suma);
	
	  printf("%d\n",k);
	
	for(i=1;i<=k;i++)
		printf("%d %d\n",G[arb[i]].x,G[arb[i]].y);
	
	fclose(stdout);
	  
	
	return 0;
}