#include<fstream.h>
using namespace std;
ifstream intrare("apm.in");
ofstream iesire("apm.out");
int n,m;
struct arc
{
	int cost,a,b;
};
arc lista[400000];
short int da[200000];
int aux[400000];
int vizitat[200000];
int grafuri[200000];
void citeste()
{
	intrare>>n>>m;
	for(int i=1;i<=m;i++)
	{
		intrare>>lista[i].a>>lista[i].b>>lista[i].cost;
	}
	for(int i=1;i<=m;i++)aux[i]=i;
}
void sort(int stanga,int dreapta)
{
	if(stanga>=dreapta)return;
	int s=1,d=0;
	int a=stanga,b=dreapta;
	while(a!=b)
	{
		if(lista[aux[a]].cost>lista[aux[b]].cost)
		{
			int c=aux[a];
			aux[a]=aux[b];
			aux[b]=c;
			if(s==1)s=0;
			else s=1;
			if(d==-1)d=0;
			else d=-1;
		}
		a+=s;b+=d;
	}
	sort(stanga,a-1);
	sort(a+1,dreapta);
}

void parcurge()
{
	int count=0;
	int suma=0;
	int ccc=0;
	for(int i=1;i<=m;i++)
	{
		int a=lista[aux[i]].a;
		int b=lista[aux[i]].b;
		if(vizitat[a]==0&&vizitat[b]==0)
		{
			count++;
			grafuri[count]=count;
			vizitat[a]=count;vizitat[b]=count;
		    da[++ccc]=aux[i];
			suma+=lista[aux[i]].cost;
		}
		else if(vizitat[a]!=0&&vizitat[b]!=0)
		{
			if(grafuri[vizitat[a]]!=grafuri[vizitat[b]])
			{
				grafuri[vizitat[b]]=grafuri[vizitat[a]];
				da[++ccc]=aux[i];
			suma+=lista[aux[i]].cost;
			}
		}
		else if(vizitat[a]==0&&vizitat[b]!=0)
		{
			vizitat[a]=vizitat[b];
			da[++ccc]=aux[i];
			suma+=lista[aux[i]].cost;
		}
		else {vizitat[b]=vizitat[a];da[++ccc]=aux[i];
			suma+=lista[aux[i]].cost;
		}
	}
	iesire<<suma<<"\n"<<ccc<<"\n";
	for(int i=1;i<=ccc;i++)
	{
		iesire<<lista[da[i]].a<<" "<<lista[da[i]].b<<"\n";
	}
}
int main()
{
	citeste();
	sort(1,m);
	parcurge();
	//afiseaza();
	return 0;
}