#include<fstream>
#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;
	ifstream f("apm.in");
	   f>>n>>m;
	   
	for(i=1;i<=m;i++)
	  { 
		f>>G[i].x>>G[i].y>>G[i].cost;
	    ord[i]=i;
	  }
	f.close();
}

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])
	  {cardinal[x]=cardinal[x]+cardinal[y];
	cardinal[y]=cardinal[x]+cardinal[y];
	 for(i=1;i<=n;i++)
	if(pad[i]==multime2)
		pad[i]=multime1;
	
	  }
	  else{
		  cardinal[x]=cardinal[x]+cardinal[y];
	cardinal[y]=cardinal[x]+cardinal[y];
	 for(i=1;i<=n;i++)
	if(pad[i]==multime1)
		pad[i]=multime2;}
		  

  for(i=1;i<=n;i++)
	if(pad[i]==multime2)
		pad[i]=multime1;
	
	/*for(i=1;i<=n;i++)
		  cout<<pad[i]<<" ";
	cout<<endl;
	system("pause");*/
}
  
	
int main()
{
	int i,suma=0,k=0;
	citire();
	
	for(i=1;i<=n;i++)
	    pad[i]=i;
	
	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];
	    }
	  
	  
	ofstream g("apm.out");
	 g<<suma<<"\n";
	
	  g<<k<<"\n";
	
	for(i=1;i<=k;i++)
	{
		g<<G[arb[i]].x<<" "<<G[arb[i]].y;
		g<<"\n";
	}
	g.close();
	  
	
	return 0;
}