#include<cstdio>
#include<fstream>
using namespace std;
int n,m,a[2000][3];
ifstream fin("apm.in");ofstream fout("apm.out");
struct graf	{int x,y,c;} g[2000],aj;
void citire()
{
	int i=1;fin>>n>>m;for(i=1;i<=m;i++)	fin>>g[i].x>>g[i].y>>g[i].c;
}
void sortare()
{
	int i,j;
	for(i=1;i<m;i++) 
	{
		for(j=i+1;j<=m;j++)	
		{
			if(g[i].c>g[j].c)	{aj=g[i];g[i]=g[j];g[j]=aj;}
		}
	}
}
void pro()
{
	int L[2000],i,j,k=0,s=0,l=1;
	for(i=1;i<=n;i++) L[i]=i;
	i=1;
	while(k<n-1)
	{
		if(L[g[i].x]!=L[g[i].y])	
		{
			L[g[i].x]=L[g[i].y];k++;s+=g[i].c;a[l][1]=g[i].x;a[l][2]=g[i].y;l++;
			for(j=1;j<=m;j++) { if(L[j]==g[i].x)	L[j]=g[i].y;}
		}
		i++;
	}
	fout<<s<<endl<<k<<endl;
	for(i=1;i<=k;i++)
		fout<<a[i][1]<<' '<<a[i][2]<<endl;
}
int main()
{
	citire();sortare();pro();return 0;
}