#include<fstream>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

# define maxM 400002

int cn,m,c[maxM],a[2][maxM],t[200002],cost;

void citire()
{
	int i;
	f>>cn>>m;
	for(i=1;i<=m;++i)
		f>>a[0][i]>>a[1][i]>>c[i];
}
void swap(int i,int j)
{
	int a1=a[0][i],a2=a[1][i],ac=c[i];
	a[0][i]=a[0][j];a[1][i]=a[1][j];c[i]=c[j];
	a[0][j]=a1;a[1][j]=a2;c[j]=ac;
}
void sift(int n,int k)
{
	int son;
	do{
		son=0;
		if(2*k<=n)
		{
			son=2*k;
			if(son<n && c[son]<c[son+1]) son++;
			if(c[son]>c[k])
			{
				swap(son,k);
				k=son;
			}
			else son=0;
		}
	}while(son);
}
void HeapSort(int n)
{
	int i;
	for(i=n/2;i;--i)
		sift(n,i);
	for(i=n;i>1;--i)
	{
		swap(i,1);
		sift(i-1,1);
	}
}
int pad(int i,int j,int k)
{
	int p;
	p=i;
	while(t[i]!=i) i=t[i];
	t[p]=i;p=j;
	while(t[j]!=j) j=t[j];
	if(i!=j)
	{		
		t[i]=j;
		cost+=c[k];
		return 1;
	}
	return 0;
}
void afisare(int i)
{
	int ok;
	ok=pad(a[0][i],a[1][i],i);
	if(i<m) afisare(i+1);
	else
		g<<cost<<'\n'<<cn-1<<'\n';
	if(ok) g<<a[0][i]<<" "<<a[1][i]<<'\n';
}
int main()
{
	int i;
	citire();
	HeapSort(m);
	for(i=1;i<=cn;i++)
		t[i]=i;
	afisare(1);
}